题意：
按顺序给出一些木棍，输出在最上面的木棍标号
题解：
一开始看到n=100000还在想怎么优化，没想出来，最后看讨论，原来暴力可以水过~
嘿嘿~用了下并查集压缩路径，在刷数组的时候会快一些~
View Code
1 #include <iostream> 2 #include <cstring> 3 #include <cstdlib> 4 #include <cstdio> 5 #include <algorithm> 6 7 #define N 110000 8 #define EPS 1e-8 9 10 using namespace std; 11 12 struct P 13 { 14 double x,y; 15 }li[N][2]; 16 17 bool vis[N]; 18 int n,fa[N]; 19 20 inline void read() 21 { 22 for(int i=1;i<=n;i++) 23 { 24 scanf("%lf%lf%lf%lf",&li[i][0].x,&li[i][0].y,&li[i][1].x,&li[i][1].y); 25 fa[i]=i; 26 } 27 } 28 29 inline double cross(const P &o,const P &p,const P &q) 30 { 31 double fx=p.x-o.x,fy=p.y-o.y,sx=q.x-o.x,sy=q.y-o.y; 32 return fx*sy-fy*sx; 33 } 34 inline bool check(int a,int b) 35 { 36 double fg1=cross(li[a][0],li[b][0],li[a][1])*cross(li[a][0],li[b][1],li[a][1]); 37 double fg2=cross(li[b][0],li[a][0],li[b][1])*cross(li[b][0],li[a][1],li[b][1]); 38 if(fg1<EPS&&fg2<EPS) return true; 39 return false; 40 } 41 42 inline int findfa(int u) 43 { 44 if(fa[u]!=u) fa[u]=findfa(fa[u]); 45 return fa[u]; 46 } 47 48 inline void go() 49 { 50 memset(vis,0,sizeof vis); 51 for(int i=1;i<=n;i++) 52 for(int j=findfa(1);j<i;j=findfa(j+1)) 53 if(check(i,j)) fa[j]=j+1,vis[j]=true; 54 printf("Top sticks:"); 55 for(int i=1,fg=0;i<=n;i++) 56 if(!vis[i]) 57 { 58 if(fg) printf(", %d",i); 59 else printf(" %d",i),fg=true; 60 } 61 puts("."); 62 } 63 64 int main() 65 { 66 while(scanf("%d",&n),n) read(),go(); 67 return 0; 68 }