捡火柴的Nova君

题目描述

南方没暖气，怕冷的的宝宝们只能用火柴取暖。然而Nova君害怕火烧到手指头，当木头梗还有一大截的时候就慌忙把火柴丢到地上踩灭了，没多久，地上就七零八落，躺着一堆木棍，有得木梗还盖在了别的上面。现在Nova君打算收拾残局，他准备一根一根捡起火柴，但他很怕多花力气，所以决定优先捡起没有被盖住的火柴梗（因为被盖住的捡起来更费力嘛），所以现在Nova君，有多少根火柴是没有被盖住的呢？

输入

多组测试数据（组数不超过100），对于每组数据，第一行为一个正整数N，表示火柴梗的根数，接下来N行，每行四个浮点数a1,a2,b1,b2，分别表示火柴梗两个端点的横纵坐标。（请用double数据类型，保证输入数据合法）

输出

对于每组数据，输出一行，表示没有被盖住的火柴序号（输出的相对顺序与输入时保持一致）

输入样例

输出样例

2
1 2 3

Hint

抽象出的线段，只要有点重合，就算是覆盖了

解题思路：
一根火柴两个端点，两个端点组成一个线段。意思就是找到没有被覆盖的火柴序号。
注意：火柴序号即火柴输入的顺序（1,2,3。。。）
姿势很多，给出结构体代码：

 1 #include <bits/stdc++.h>
 2 #define eps 1e-6
 3 #define MAX 100010
 4 
 5 using namespace std;
 6 
 7 int sgn(double x)
 8 {
 9     if(fabs(x)<eps)
10         return 0;
11     if(x<0)
12         return -1;
13     else return 1;
14 }
15 
16 struct Point
17 {
18     double x,y;
19     Point() {}
20     Point(double x1,double y1)
21     {
22         x=x1;
23         y=y1;
24     }
25     Point operator -(Point b)
26     {
27         return Point(x-b.x,y-b.y);
28     }
29     double operator ^(const Point b)
30     {
31         return x*b.y-y*b.x;
32     }
33     double operator *(Point b)
34     {
35         return x*b.x+y*b.y;
36     }
37 };
38 
39 struct Line
40 {
41     Point start,over;
42     Line() {}
43     Line(Point start1,Point over1)
44     {
45         start=start1;
46         over=over1;
47     }
48 };
49 
50 bool cs(Line l1,Line l2)
51 {
52     return
53         ( max(l1.start.x,l1.over.x)>=min(l2.start.x,l2.over.x)
54         &&max(l2.start.x,l2.over.x)>=min(l1.start.x,l1.over.x)
55         &&max(l1.start.y,l1.over.y)>=min(l2.start.y,l2.over.y)
56         &&max(l2.start.y,l2.over.y)>=min(l1.start.y,l1.over.y)
57         &&sgn((l2.start-l1.start)^(l1.over-l1.start))*sgn((l2.over-l1.start)^(l1.over-l1.start))<=0
58         &&sgn((l1.start-l2.start)^(l2.over-l2.start))*sgn((l1.over-l2.start)^(l2.over-l2.start))<=0 );
59 }
60 
61 Line line[MAX];
62 bool flag[MAX];
63 int main()
64 {
65     int n,i,j;
66     double x1,y1,x2,y2;
67     while(~scanf("%d",&n))
68     {
69         for(i=1;i<=n;i++)
70         {
71             scanf("%lf %lf %lf %lf",&x1,&y1,&x2,&y2);
72             line[i]=Line(Point(x1,y1),Point(x2,y2));
73             flag[i]=true;
74         }
75         for(i=1;i<=n;i++)
76         {
77             for(j=i+1;j<=n;j++)
78                 if(cs(line[i],line[j]))
79                 {
80                     flag[i]=false;
81                     break;
82                 }
83         }
84         for(i=1;i<=n;i++)
85         {
86             if(flag[i])
87             {
88                 printf("%d ",i);
89             }
90         }
91         printf("
");
92     }
93     return 0;
94 }