题目大意：给定一个凸，，有一些边不能走，若两条边相交可以变道，求最短路
MD这水题看错题困扰了我多年= = 一直以为是补图的最短路……
最短路显然是半平面交 从一个点出发的所有边中只有最后一条可能在半平面交上 然后就完事了啊= =
;struct Point{double x,y;Point() {}Point(double _,double __):x(_),y(__) {}friend istream& operator >> (istream &_,Point &p){scanf(“%lf%lf”,&p.x,&p.y);return _;}friend Point operator + (const Point &p1,const Point &p2){return Point(p1.x+p2.x,p1.y+p2.y);}friend Point operator – (const Point &p1,const Point &p2){return Point(p1.x-p2.x,p1.y-p2.y);}* (const Point &p1,const Point &p2){return p1.x*p2.y-p1.y*p2.x;}friend Point operator * (const Point &p,double rate){return Point(p.x*rate,p.y*rate);}friend double Distance (const Point &p1,const Point &p2){return sqrt( (p1.x-p2.x)*(p1.x-p2.x) + (p1.y-p2.y)*(p1.y-p2.y) ) ;}}points[M];struct Line{Point p,v;Line() {}Line(const Point &_,const Point &__):p(_),v(__) {}friend Point Get_Intersection(const Line &l1,const Line &l2){Point u=l1.p-l2.p;double temp=(l2.v*u)/(l1.v*l2.v);return l1.p+l1.v*temp;}friend bool On_Left(const Line &l,const Point &p){return (l.p-p)*l.v > EPS ;}}stack[M];int top;int n,m,now;vector<int> a[M];double ans;void Insert(const Line &l){while( top>=2 && On_Left(l,Get_Intersection(stack[top-1],stack[top])) )top–;stack[++top]=l;}int main(){int i,j,k,x,y;cin>>n>>m;for(i=1;i<=n;i++)cin>>points[i];for(i=1;i<=m;i++){scanf(“%d%d”,&x,&y);if(x>y) swap(x,y);a[x].push_back(y);}for(i=1;i<=n;i++)sort(a[i].begin(),a[i].end());for(i=1;i<=n;i++){for(j=n,k=a[i].size()-1;j>now&&k>=0;j–,k–)if(a[i][k]!=j)break;if(j>now)Insert(Line(points[i],points[now=j]-points[i]));}Point last=points[1];for(i=2;i<=top;i++){Point temp=Get_Intersection(stack[i-1],stack[i]);ans+=Distance(last,temp);last=temp;}ans+=Distance(last,points[n]);printf(“%.9lf\n”,ans);return 0;}
一个人最大的破产是绝望，最大的资产是希望。
