筷子在古代叫箸或筯（箸者，助也，意思是帮助吃饭的工具。另：在地区、还有地区的当地人仍称筷子为箸，在闽南语地区念tî、拼音为chī，温州市区念dzei），又叫梜。曾引用的《》说：“起于吴中。凡舟行讳住讳翻，故呼箸为快子”（住和箸同音）。人类使用筷子的历史可以追溯到三千年以前，《·曲礼上》就有“饭黍母以箸”和“羹之有菜者用梜”的记载。由考古学提供的证据而言，筷子的出现晚于匙羹，同样原因，由于人们想做某种工具以方便取得烫热的熟食，所以筷子的发明跟原始农业和陶器的运用和发展有着直接关系。

 筷子是何人发明，何时诞生，历代虽有很多传说，但实在难以考究。中国人从古至今都视筷子为自然沿袭下来的家常用品，对其的由来和发展只有少量的记载，或是有关的书籍早已失传。

 

  我们玩的游戏很简单，地面上有很多筷子，它们互相交叠在一起，我们需要找到的是所有的最上方的筷子，并将其按照编号从小到大顺次输出。

 输入有N行，每一行有4个数据，可以表示为（x1,y1,x2,y2），这里表示一根筷子的起始点。后面一行的筷子总是叠放在前面一个筷子的上方。输出主要是按照编号的大小顺序输出在最上方的筷子的编号。

  Solve:

 

 1  #include<iostream>

 2  #include<cstdio>

 3  #include<cstring>

 4  

using 

namespace std;

 5  

 6  

//

将筷子的总数定义到10万左右的数量级，再定义一个很小很小的数，因为是double类型的，所以要考虑到浮点误差

 7 

 

const 

int maxn=

100000+

5;

 8  

const 

double eps=1e-

10;

 9  

10  

//

定义一个(x,y)的结构体

11 

 

struct point

12  {

13    

double x,y;       

14  };

15  

16  

//

每一个筷子都有始端和末端，我们用p[maxn]和b[maxn]来装填这两端的值

17 

 point p[maxn],b[maxn];

18  

//

这里用0表示没有和任何一个筷子相交，只要有一个以上的筷子与其相交，就表示为1，所以是bool逻辑的

19 

 

bool ans[maxn];

20  

21  

//

double型的计算最小值函数

22 

 

double min(

double a,

double b)

23  {

24    

return a<b ? a:b;       

25  }

26  

27  

//

double型的计算最大值函数

28 

 

double max(

double a,

double b)

29  {

30    

return a>b ? a:b;       

31  }

32  

33  

//

考虑是否相交

34 

 

bool inter(point a,point b,point c,point d)

35  {

36    

//

我们考虑到如果某个筷子的两端的横/纵坐标都小于（或者大于）另外一个筷子的横/纵坐标，则可以排除是inter的情况

37 

   

if( min(a.x, b.x)>max(c.x,d.x)||

38        min(a.y, b.y)>max(c.y,d.y)||

39        min(c.x, d.x)>max(a.x,b.x)||

40        min(c.y, d.y)>max(a.y, b.y) )

41     

return 

0;

42 

43     

double h,i,j,k;

44 

45     h=(b.x-a.x)*(c.y-a.y)-(b.y-a.y)*(c.x-a.x);

46     i=(b.x-a.x)*(d.y-a.y)-(b.y-a.y)*(d.x-a.x);

47     j=(d.x-c.x)*(a.y-c.y)-(d.y-c.y)*(a.x-c.x);

48     k=(d.x-c.x)*(b.y-c.y)-(d.y-c.y)*(b.x-c.x);

49     

50     

//

用这四个变量判断是否相交，因为浮点数存在一定的误差，所以利用eps来修补一下

51 

    

return h*i<=eps&&j*k<=eps;

52  }

53  

54  

int main()

55  {

56    

int n,i,j;

57    

int res[maxn];

58    

//

如果遇到输入为0的情况，就退出

59 

   

while(cin>>n,n)

60    {

61      

//

将

62 

     memset(ans,

0,

sizeof(ans));

63      

for(i=

0;i<n;i++)

64      {

65        

//

输入每个筷子的始端p和末端b的坐标值

66 

       cin>>p[i].x>>p[i].y>>b[i].x>>b[i].y;               

67      }               

68      

for(i=

0;i<n;i++)

69      {

70        

for(j=i+

1;j<n;j++)

71        {

72          

//

判断筷子i与筷子j是不是会相交，如果会相交的话，就予以记录

73 

         

if(inter(p[i],b[i],p[j],b[j]))

74          {

75            ans[i]=

1;

76            

break;                              

77          }                  

78        }                

79      }

80      

int ct=

0;

81      cout<<

"

Top sticks:

";

82      

for(i=

0;i<n;i++)

83      {

84        

//

如果第i个筷子没有被它之后的任何一个筷子相交的话（之前的不用判断，因为即使是相交的话也肯定会在它下面的）

85 

       

if(!ans[i])

86          

//

这里要注意是i+1，因为数组是由0开始计数的

87 

         res[ct++]=i+

1;

88      }

89      

for(i=

0;i<ct-

1;i++)

90        cout<<res[i]<<

"

,

";

91      

//

最后一个单独输出

92 

     cout<<res[ct-

1]<<

"

.

"<<endl;  

93    }

94    

return 

0;    

95  }