Time Limit: 4000/2000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 2673 Accepted Submission(s): 975
#include<stdio.h> #include<iostream> #include<string.h> #include<math.h> #include<algorithm> using namespace std; const int N = 100005; struct Point{ double x,y; }p[2*N]; ///叉积 double mult(Point a, Point b, Point c) { return (a.x-c.x)*(b.y-c.y)-(b.x-c.x)*(a.y-c.y); } ///a, b为一条线段两端点c, d为另一条线段的两端点 相交返回true, 不相交返回false bool isCross(Point a, Point b, Point c, Point d) { if (max(a.x,b.x)<min(c.x,d.x))return false; if (max(a.y,b.y)<min(c.y,d.y))return false; if (max(c.x,d.x)<min(a.x,b.x))return false; if (max(c.y,d.y)<min(a.y,b.y))return false; if (mult(c, b, a)*mult(b, d, a)<0)return false; if (mult(a, d, c)*mult(d, b, c)<0)return false; return true; } bool under[N]; ///记录哪些stick在下面 int ans[N]; int main() { int n; while(scanf("%d",&n)!=EOF,n){ memset(under,false,sizeof(under)); int k=1; for(int i=1;i<=n;i++){ scanf("%lf%lf%lf%lf",&p[k].x,&p[k].y,&p[k+1].x,&p[k+1].y); k+=2; } for(int i=1;i<=n;i++){ for(int j=i+1;j<=n;j++){ if(isCross(p[2*i-1],p[2*i],p[2*j-1],p[2*j])) { under[i]=true; break; } } } printf("Top sticks: "); int t=0; for(int i=1;i<=n;i++){ if(!under[i]) ans[t++]=i; } for(int i=0;i<t-1;i++){ printf("%d, ",ans[i]); } printf("%d.\n",ans[t-1]); } return 0; }
原文:http://www.cnblogs.com/liyinggang/p/5427486.html