题目大意：依次给出若干条线段，后给出的线段是后放置的，可能会“盖在”先前的线段上。求所有没有被盖住的线段。
题解
容易知道最后一根放上去的线段肯定不会被盖住。那么只需要对当前线段不断向后枚举，看看是否会被后来的线段盖住就行了。
注意线段盖住可能有覆盖一部分的情况，这个要做特殊判定。
时间复杂度理论上是$O(n^2)$的，但因为数据是随机的所以比较快。1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
using namespace std;
double eps = 1e-8;
const double pi = acos(-1.0);
int cmp(double x){
if(fabs(x) < eps) return 0;
return (x > 0 ? 1: -1);
}
struct Point{
double x, y;
Point(){}
Point(double _x, double _y){
x = _x, y = _y;
}
void input(){
scanf("%lf%lf", &x, &y);
}
void output(){
printf("%.3lf %.3lf\n", x, y);
}
friend bool operator == (const Point &pa, const Point &pb) {
return cmp(pa.x - pb.x) == 0 && cmp(pa.y - pb.y) == 0;
}
friend bool operator < (const Point &pa, const Point &pb) {
return cmp(pa.x - pb.x) == 0 ? cmp(pa.y - pb.y) < 0: pa.x < pb.x;
}
friend Point operator + (const Point &pa, const Point &pb) {
return Point(pa.x + pb.x, pa.y + pb.y);
}
friend Point operator - (const Point &pa, const Point &pb) {
return Point(pa.x - pb.x, pa.y - pb.y);
}
friend Point operator * (const Point &pa, const double &rat) {
return Point(pa.x * rat, pa.y * rat);
}
friend Point operator / (const Point &pa, const double &rat) {
return Point(pa.x / rat, pa.y / rat);
}
//逆时针旋转
friend Point operator << (const Point &pa, const double &rat) {
double sine = sin(rat), cosi = cos(rat);
return Point(pa.x * cosi - pa.y * sine, pa.x * sine + pa.y * cosi);
}
//顺时针旋转
friend Point operator >> (const Point &pa, const double &rat) {
double sine = sin(rat), cosi = cos(rat);
return Point(pa.x * cosi + pa.y * sine, pa.y * cosi - pa.x * sine);
}
double norm() const{
return hypot(x, y);
}
double sqr() const{
return x * x + y * y;
}
};
double dot(const Point &pa, const Point &pb) {
return pa.x * pb.x + pa.y * pb.y;
}
double cross(const Point &pa, const Point &pb) {
return pa.x * pb.y - pa.y * pb.x;
}
double dist(const Point &pa, const Point &pb) {
return hypot(pa.x - pb.x, pa.y - pb.y);
}
//线段之间角
double rad(const Point &pa, const Point &pb){
return acos(dot(pa, pb) / (pa.norm() * pb.norm()));
}
//线段共同点之间角
double rad(const Point &pa, const Point &pb, const Point &pc){
return acos(dot(pa - pc, pb - pc) / ((pa - pc).norm() * (pb - pc).norm()));
}
struct Segment{
Point s, e;
Segment() {}
Segment(const Point &st, const Point &ed){
if(st < ed) s = st, e = ed;
else s = ed, e = st;
}
friend bool operator == (const Segment &sa, const Segment &sb) {
return sa.s == sb.s && sa.e == sb.e;
}
friend double operator * (const Segment &sa, const Segment &sb) {
return dot(sa.e - sa.s, sb.e - sb.s);
}
friend bool operator / (const Segment &sa, const Segment &sb) {
return cross(sa.e - sa.s, sb.e - sb.s);
}
friend Point operator ^ (const Segment &sa, const Segment &sb){
double det1 = cross(sa.s - sb.s, sb.e - sb.s);
double det2 = cross(sa.e - sb.s, sb.e - sb.s);
return (sa.e * det1 - sa.s * det2) / (det1 - det2);
}
bool includes(const Point &pa) const{
return cmp(cross(pa - s, pa - e)) == 0 && cmp(dot(pa - s, pa - e)) <= 0;
}
//严格在内部
bool str_includes(const Point &pa) const{
return cmp(cross(pa - s, pa - e)) == 0 && cmp(dot(pa - s, pa - e)) < 0;
}
bool parallel(const Segment &sa) const{
return cmp(cross(sa.e - sa.s, e - s)) == 0;
}
double len() const{
return dist(s, e);
}
};
Segment make_seg(const Point &st, const Point &ed){
return Segment(st, ed);
}
int n, ans[1005], tot = 0;
Segment seg[100005];
int main(){
while(scanf("%d", &n) == 1){
if(!n) break;
for(int i = 1; i <= n; ++i){
Point p1, p2;
p1.input(), p2.input();
seg[i] = make_seg(p1, p2);
}
tot = 0, ans[++tot] = n;
for(int i = n - 1; i >= 1; --i){
int flag = 1;
for(int j = n; j > i; --j){
if(seg[i].parallel(seg[j])){
if(seg[i].str_includes(seg[j].s) || seg[i].str_includes(seg[j].e)){
flag = 0;
break;
}
}else{
Point pp = seg[i] ^ seg[j];
if(seg[i].str_includes(pp) && seg[j].str_includes(pp)){
flag = 0;
break;
}
}
}
if(flag) ans[++tot] = i;
}
printf("Top sticks: ");
for(int i = tot; i > 1; --i)
printf("%d, ", ans[i]);
printf("%d.\n", ans[1]);
}
return 0;
}