---恢复内容开始---
题目链接:https://vjudge.net/problem/POJ-1696
题意：有n个点，规定起点，每次只能向左走，不能与之前的路径交叉，求最多能经过几个点。
思路：
其实这题因为起点的y坐标最小，那么经过的点数一定就是所有的点数n，然后显然我们优先选择偏移角度最小的点作为后继，也就是极角最小，那么每次选择一个点后都按极角升序排一次即可。我的代码是遍历了一遍，因为数据量本身很小。代码有些乱，main函数前都是模板。
AC code：
#include<cstdio> #include<algorithm> #include<cmath> #include<cstdlib> using namespace std; const double eps=1e-8; const double inf=1e20; int sgn(double x){ if(abs(x)<eps) return 0; if(x<0) return -1; return 1; } struct Point{ double x,y; Point(){} Point(double xx,double yy):x(xx),y(yy){} Point operator + (const Point& b)const{ return Point(x+b.x,y+b.y); } Point operator - (const Point& b)const{ return Point(x-b.x,y-b.y); } double operator * (const Point& b)const{ return x*b.x+y*b.y; } double operator ^ (const Point& b)const{ return x*b.y-b.x*y; } //绕原点旋转角度b（弧度值），后x、y的变化 void transXY(double b){ double tx=x,ty=y; x=tx*cos(b)-ty*sin(b); y=tx*sin(b)+ty*cos(b); } }; struct Line{ Point s,e; Line(){} Line(Point ss,Point ee){ s=ss,e=ee; } //两直线相交求交点 //第一个值为0表示直线重合，为1表示平行，为2表示相交 //只有第一个值为2时，交点才有意义 pair<int,Point> operator &(const Line &b)const{ Point res = s; if(sgn((s-e)^(b.s-b.e)) == 0) { if(sgn((s-b.e)^(b.s-b.e)) == 0) return make_pair(0,res);//重合 else return make_pair(1,res);//平行 } double t = ((s-b.s)^(b.s-b.e))/((s-e)^(b.s-b.e)); res.x += (e.x-s.x)*t; res.y += (e.y-s.y)*t; return make_pair(2,res); } }; //判断线段相交 bool inter(Line l1,Line l2){ return max(l1.s.x,l1.e.x)>=min(l2.s.x,l2.e.x)&& max(l2.s.x,l2.e.x)>=min(l1.s.x,l1.e.x)&& max(l1.s.y,l1.e.y)>=min(l2.s.y,l2.e.y)&& max(l2.s.y,l2.e.y)>=min(l1.s.y,l1.e.y)&& sgn((l1.s-l2.s)^(l2.e-l2.s))*sgn((l1.e-l2.s)^(l2.e-l2.s))<=0&& sgn((l2.s-l1.s)^(l1.e-l1.s))*sgn((l2.e-l1.s)^(l1.e-l1.s))<=0; } double dis(Point a,Point b){ return sqrt((b-a)*(b-a)); } //判断点在线段上 bool OnSeg(Point P,Line L){ return sgn((L.s-P)^(L.e-P))==0&& sgn((P.x-L.s.x)*(P.x-L.e.x))<=0&& sgn((P.y-L.s.y)*(P.y-L.e.y))<=0; } //判断点在凸多边形内，复杂度O(n) //点形成一个凸包，而且按逆时针排序（如果是顺时针把里面的<0改为>0） //点的编号:0~n-1 //返回值： //-1:点在凸多边形外 //0:点在凸多边形边界上 //1:点在凸多边形内 int inConvexPoly(Point a,Point p[],int n){ for(int i=0;i<n;++i) if(sgn((p[i]-a)^(p[(i+1)%n]-a))<0) return -1; else if(OnSeg(a,Line(p[i],p[(i+1)%n]))) return 0; return 1; } //判断点在任意多边形内,复杂度O(n) //射线法，poly[]的顶点数要大于等于3,点的编号0~n-1 //返回值 //-1:点在凸多边形外 //0:点在凸多边形边界上 //1:点在凸多边形内 int inPoly(Point a,Point p[],int n){ int cnt=0; Line ray,side; ray.s=a; ray.e.y=a.y; ray.e.x=-inf; for(int i=0;i<n;++i){ side.s=p[i]; side.e=p[(i+1)%n]; if(OnSeg(a,side)) return 0; if(sgn(side.s.y-side.e.y)==0) continue; if(OnSeg(side.s,ray)){ if(sgn(side.s.y-side.e.y)>0) ++cnt; } else if(OnSeg(side.e,ray)){ if(sgn(side.e.y-side.s.y)>0) ++cnt; } else if(inter(ray,side)) ++cnt; } if(cnt%2==1) return 1; else return -1; } const int maxn=55; Point pt[maxn]; Line line[maxn]; int T,n,cnt,ans[maxn],vis[maxn]; int main(){ scanf("%d",&T); double x,y; while(T--){ scanf("%d",&n); for(int i=1;i<=n;++i) vis[i]=0; int tmp; double Min=inf; for(int i=1;i<=n;++i){ int t; scanf("%d%lf%lf",&t,&pt[i].x,&pt[i].y); if(pt[i].y<Min){ Min=pt[i].y; tmp=i; } } cnt=0; line[++cnt]=Line(Point(0,pt[tmp].y),pt[tmp]); ans[cnt]=tmp; vis[tmp]=1; while(1){ int tmp=0; double Max=-2.0; for(int i=1;i<=n;++i){ if(vis[i]) continue; if(sgn((pt[i]-line[cnt].e)^(line[cnt].e-line[cnt].s))>0) continue; int f=1; for(int j=1;j<cnt;++j) if(inter(line[j],Line(line[cnt].e,pt[i]))){ f=0;break; } if(!f) continue; double now=(pt[i]-line[cnt].e)*(line[cnt].e-line[cnt].s)/dis(pt[i],line[cnt].e)/dis(line[cnt].e,line[cnt].s); if(now>Max){ Max=now,tmp=i; } } if(!tmp) break; vis[tmp]=1; line[++cnt]=Line(line[cnt-1].e,pt[tmp]); ans[cnt]=tmp; } printf("%d",cnt); for(int i=1;i<=cnt;++i) printf(" %d",ans[i]); printf(" "); } return 0; }