题目链接：https://vjudge.net/problem/POJ-2653
参考自kuangbin：https://www.cnblogs.com/kuangbin/p/3189750.html
线段是否相交：
1 /************************************************************************* 2 > File Name: poj2653.cpp 3 # File Name: poj2653.cpp 4 # Author : xiaobuxie 5 # QQ : 760427180 6 # Email:[email protected] 7 # Created Time: 2019年09月20日 星期五 17时46分50秒 8 ************************************************************************/ 9 10 #include<iostream> 11 #include<cstdio> 12 #include<map> 13 #include<cmath> 14 #include<cstring> 15 #include<set> 16 #include<queue> 17 #include<vector> 18 #include<algorithm> 19 using namespace std; 20 typedef long long ll; 21 #define inf 0x3f3f3f3f 22 #define eps 1e-8 23 #define pq priority_queue<int,vector<int>,greater<int> > 24 ll gcd(ll a,ll b){ 25 if(a<b) return gcd(b,a); 26 return b==0?a:gcd(b,a%b); 27 } 28 29 const int N=1e5+9; 30 struct Point{ 31 double x,y; 32 Point(){} 33 Point(double _x,double _y){ 34 x=_x; y=_y; 35 } 36 Point operator - (const Point& b)const{ 37 return Point(x-b.x,y-b.y); 38 } 39 double operator * (const Point& b)const{ 40 return x*b.x+y*b.y; 41 } 42 double operator ^ (const Point& b)const{ 43 return x*b.y-b.x*y; 44 } 45 }; 46 struct Line{ 47 Point s,e; 48 Line(){} 49 Line(Point _s,Point _e){ 50 s=_s; e=_e; 51 } 52 }L[N]; 53 int sgn(double x){ 54 if(fabs(x)<eps) return 0; 55 if(x<0) return -1; 56 return 1; 57 } 58 int ans[N]; 59 60 bool insert(Line l1,Line l2){ 61 return 62 max(l1.s.x,l1.e.x) >= min(l2.s.x,l2.e.x) && 63 max(l2.s.x,l2.e.x) >= min(l1.s.x,l1.e.x) && 64 max(l1.s.y,l1.e.y) >= min(l2.s.y,l2.e.y) && 65 max(l2.s.y,l2.e.y) >= min(l1.s.y,l1.e.y) && 66 sgn((l2.s-l1.s)^(l1.e-l1.s))*sgn((l2.e-l1.s)^(l1.e-l1.s))<=0 && 67 sgn((l1.s-l2.s)^(l2.e-l2.s))*sgn((l1.e-l2.s)^(l2.e-l2.s))<=0; 68 } 69 int main(){ 70 int n; 71 double x1,x2,y1,y2; 72 int cnt=0; 73 while(~scanf("%d",&n) && n){ 74 cnt=0; 75 for(int i=1;i<=n;++i){ 76 scanf("%lf %lf %lf %lf",&x1,&y1,&x2,&y2); 77 L[i]=Line(Point(x1,y1),Point(x2,y2)); 78 } 79 for(int i=1;i<=n;++i){ 80 bool ok=1; 81 for(int j=i+1;j<=n;++j){ 82 if(insert(L[i],L[j])){ 83 ok=0; 84 break; 85 } 86 } 87 if(ok) ans[++cnt]=i; 88 } 89 printf("Top sticks: "); 90 for(int i=1;i<cnt;++i) printf("%d, ",ans[i]); 91 printf("%d.\n",ans[cnt]); 92 } 93 return 0; 94 }