挑棍子-蒲公英云

挑棍子

 Stan有n根不同长度的棍子。他随机地一次性将它们扔到地上，扔完后，Stan想找到那些顶层的棍子，也就是那些没有其他棍子压在上面的棍子。他注意到最后扔的棍子总是顶层的，而他想知道所有顶层的棍子。棍子非常非常薄，其厚度可以忽略。

【输入形式】

   输入由若干测试用例组成，每个用例以一个整数n(1<=n<=100000)开始，表示棍子数。每个用例接下来的n行包含4个数，表示棍子端点的平面坐标，以Stan扔出的棍子的顺序列出。假定不超过1000根顶层棍子，n=0表示输入结束。

【输出形式】

  对于每个输入用例，按照样例格式列出顶层棍子。顶层棍子按照扔出的顺序列出，图片对应输入中的第一个用例。

【样例输入】

【样例输出】

Top sticks: 2,4,5
Top sticks: 1,2,3
1   :  #include<iostream> 2   :  using namespace std; 3  1 :  int main() 4   :  { 5   :      int n,i,j; 6  1 :      int x1,x2,x3,x4,y1,y2,y3,y4,shuchu[100]={0},s=0; 7   :      bool xiangjiao(int,int,int,int,float,float,int,int); 8  1 :      float z[100][5]={0},k1,k2; 9   :      for(;;){ 10  3 :          cin>>n; 11  3 :          if(n==0) break; 12  10 :          for(i=0;i<n;i++) 13  40 :           for(j=0;j<4;j++)  14  32 :             cin>>z[i][j]; 15  8 :          for(i=0;i<n-1;i++){ 16  6 :               x1=z[i][0];y1=z[i][1]; 17  6 :               x2=z[i][2];y2=z[i][3]; 18  6 :                  k1=(y1-y2)*1.0/(x1-x2); 19  13 :               for(j=i+1;j<n;j++){ 20  9 :                  x3=z[j][0];y3=z[j][1]; 21  9 :               x4=z[j][2];y4=z[j][3]; 22  9 :                  k2=(y3-y4)*1.0/(x3-x4); 23  9 :                  z[i][4]=xiangjiao(x1,y1,x3,y3,k1,k2,x2,x4); 24  9 :                  if(z[i][4]==1) break; 25   :              } 26   :          } 27  10 :          for(i=0;i<n;i++){ 28  8 :              if(z[i][4]==0){ 29  6 :                  shuchu[s]=i+1; 30  6 :                  s++; 31   :              } 32   :          } 33  2 :          cout<<"Top sticks: "; 34  8 :          for(i=0;i<s;i++){ 35  6 :              if(i==s-1) cout<<shuchu[i]<<endl; 36  4 :              else cout<<shuchu[i]<<','; 37   :          } 38  2 :          s=0; 39  10 :          for(i=0;i<n;i++){ 40  8 :              z[i][4]=0; 41   :          }  42  2 :      } 43  1 :  }  44  9 :  bool xiangjiao(int x1,int y1,int x3,int y3,float k1,float k2,int x2,int x4) 45   :  { 46   :      float x; 47  9 :      x=(k1*x1-y1-k2*x3+y3)/(k1-k2); 48  9 :      if(x>=x1&&x<=x2&&x>=x3&&x<=x4) return 1; 49  7 :      else return 0; 50  3 :  }