额，看不懂题意，我以为是求一个凸壳之类的东西。。瞬间就吓虚了。。
其实就是搞一个和后面的线段没有交点就行。。。23333
而且还是随便暴力，，，，，2333扒了一发题解压压惊2333
1 #include<cstdio> 2 #include<cstring> 3 #include<cmath> 4 #define N 100005 5 #define inf 0x3f3f3f3f 6 #define eps 1e-8 7 using namespace std; 8 int ans[N],cnt,n; 9 bool cov[N]; 10 struct point{double x,y;}; 11 struct line{point a,b;}a[N]; 12 point vec(point a, point b) 13 { 14 point t; t.x=a.x-b.x; t.y=a.y-b.y; return t; 15 } 16 double cross(point a, point b) 17 { 18 return a.x*b.y-a.y*b.x; 19 } 20 double turn(point p1, point p2, point x) 21 { 22 return cross(vec(x,p1),vec(p2,p1)); 23 } 24 bool cover(int i, int j) 25 { 26 if (turn(a[i].a,a[i].b,a[j].a)*turn(a[i].a,a[i].b,a[j].b)>0) return 0; 27 if (turn(a[j].a,a[j].b,a[i].a)*turn(a[j].a,a[j].b,a[i].b)>0) return 0; 28 return 1; 29 } 30 void solve() 31 { 32 printf("Top sticks: "); cnt=0; 33 for (int i=1; i<=n; i++) 34 { 35 bool flag=0; 36 for (int j=i+1; j<=n; j++) 37 { 38 if (cover(i,j)) {flag=1; break;} 39 } 40 if (!flag) ans[++cnt]=i; 41 } 42 for (int i=1; i<cnt; i++) printf("%d, ",ans[i]); 43 printf("%d",ans[cnt]); 44 puts("."); 45 } 46 int main() 47 { 48 while (scanf("%d",&n) && n) 49 { 50 for (int i=1; i<=n; i++) 51 scanf("%lf%lf%lf%lf",&a[i].a.x,&a[i].a.y,&a[i].b.x,&a[i].b.y); 52 solve(); 53 } 54 return 0; 55 }