2017 Multi-University Training Contest - Team 9 1003&&HDU 6163 CSGO【计算几何】
2017 Multi-University Training Contest - Team 9 1003&&HDU 6163 CSGO【计算几何】
CSGO
Time Limit: 20000/10000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others) Total Submission(s): 127 Accepted Submission(s): 20
Problem Description
Senior Pan is crazy about CSGO and she is so skilled. She can kill every enemy she spots at the same time, even if they are in different positions. There are some walls in a map. The locations of enemies are represented by some points and walls are represented by some line segments in the XY plane. The position of senior Pan is also described as a point. Senior Pan can spot an enemy if and only if the segment between them doesn’t intersect with any wall segment. But if there are other enemies on this segment, she can kill all of them. For some given positions, senior Pan wants to know how many enemies she can kill in these positions. Your Task is to write a program to figure it out.
Input
∙ The input contains multiple test cases, each of them are described below. ∙ The first line contains three integers N, M, Q representing respectively the number of enemies, the number of walls and the number of positions senior Pan chooses. For the next N lines, each line contain two integers X and Y, indicating the location of enemies is (X, Y). The next M lines, each line contain four integers X1, Y1, X2, Y2, indicating two endpoints of the wall are (X1, Y1) and (X2, Y2). The last Q lines, each line contain two integers X and Y, indicating the location of senior Pan chooses is (X, Y). ∙ You can assume that walls don’t intersect even if in their endpoints, no enemies have the same location and no enemies are in walls. ∙ N, M <= 10 ^ 4. ∙ Q <= 12. ∙ -10 ^ 6 <= X, Y, X1, Y1, X2, Y2 <= 10 ^ 6
Output
For each test case, output "Case #x: " in the first line (without quotes). For next Q lines, each line output a number which represents the number of enemies senior Pan can kill in her i-th chosen location.
Sample Input
3 2 1
1 1
2 2
-1 1
0 1 -1 0
2 -2 2 0
0 0
5 4 2
29 -8
19 33
-46 -44
-38 19
9 -20
40 45 38 18
9 -32 -8 46
33 20 35 -19
22 17 -5 40
19 -38
-17 -21Sample Output
Case #1:
2
Case #2:
3
2Source
2017 Multi-University Training Contest - Team 9
题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=6163
分析： 平面上有一些点和一些线段，保证这些线段互不相交，点不在线段上。 每次问从一个点能看到多少个点。一个点能看到另一点当且仅当这两点连线的线段不和任何一个已知的线段相交。（这里的相交均指非规范相交） 每次以询问点为极点极角排序。线段两端点拆成两个事件，一次出现，一次消失。对于枚举的某一个角度，能否看见当前角度的点仅取决于当前角度上离极点最近的线段，由于保证线段不相交，一条线段在插入时和还存在线段的相对位置是不会改变的，所以可以用set维护，每次先处理当前角度上所有的点是否被线段遮挡就可以了。
复杂度是O（Q(N + M)log(N + M)）。
下面给出AC代码：
1 #include<bits/stdc++.h>
2
3 using namespace std;
4 const int N = 11000;
5 const double eps = 1e-10;
6 const double pi = acos(-1.0);
7 typedef complex<double> Point;
8
9 double Det(const Point & a, const Point & b) {return (conj(a) * b).imag();}
10 double Dot(const Point & a, const Point & b) {return (conj(a) * b).real();}
11 int sgn(double x) {if(fabs(x) < eps) return 0; if(x > eps) return 1; return -1;}
12
13 double _ang;
14 Point ori = (Point) {0, 0};
15 struct Line :public vector<Point>{
16 double k;
17 Line(){}
18 Line(Point a, Point b){
19 push_back(a), push_back(b);
20 k = atan2((b - a).imag(), (b - a).real());
21 }
22 };
23 Point Vec(Line a) {return a[1] - a[0];}
24 Point LineIntersection(const Line & a, const Line & b){
25 double k1 = Det(Vec(a), Vec(b));
26 double k2 = Det(Vec(b), a[0] - b[0]);
27 if(!sgn(k1)){
28 if(sgn(abs(a[1] - b[0]) - abs(a[0] - b[0])) > 0) return a[0];
29 else return a[1];
30 }
31 return a[0] + Vec(a) * k2 / k1;
32 }
33
34 bool operator < (const Line & a, const Line & b){
35 Line cur = (Line) {ori, (Point) {cos(_ang), sin(_ang)}};
36 if(sgn(abs(LineIntersection(a, cur)) - abs(LineIntersection(b, cur))) < 0) return 1;
37 return 0;
38 }
39
40 struct Event{
41 double k;
42 int id, typ;
43 bool operator < (const Event & a) const{
44 if(sgn(k - a.k)) return k < a.k;
45 return typ < a.typ;
46 }
47 };
48
49 double CalcAng(const Point & a) {return atan2(a.imag(), a.real());}
50 Point p[N];
51 Line w[N], seg[N];
52 Event e[N << 3];
53
54 int q, n, m, tot;
55 set<Line> s;
56 int rec[N];
57
58 int Calc(int x){
59 tot = 0;
60 s.clear();
61 for(int i = 1; i <= n; i ++)
62 e[++ tot] = (Event){CalcAng(p[i] - p[x]), i, 1};
63
64 bool flag = 0;
65 for(int i = 1; i <= m; i++){
66 seg[i] = (Line) {w[i][0] - p[x], w[i][1] - p[x]};
67 if(sgn(CalcAng(seg[i][0]) - CalcAng(seg[i][1])) > 0) swap(seg[i][0], seg[i][1]);
68 flag = 1;
69 if(sgn(Det(Vec(seg[i]), Point(-1, 0))) != 0 && sgn(abs(CalcAng(seg[i][0]) - CalcAng(seg[i][1])) - pi) > 0) flag = 0;
70 if(flag) e[++ tot] = (Event) {CalcAng(seg[i][0]), i, 0}, e[++tot] = (Event) {CalcAng(seg[i][1]), i, 2};
71 else{
72 e[++ tot] = (Event) {-pi, i, 0};
73 e[++ tot] = (Event) {CalcAng(seg[i][0]), i, 2};
74 e[++ tot] = (Event) {CalcAng(seg[i][1]), i, 0};
75 e[++ tot] = (Event) {pi, i, 2};
76 }
77 }
78
79 sort(e + 1, e + tot + 1);
80 int cnt = 0;
81 Point dir, dd;
82 Line t;
83 for(int i = 1; i <= tot; i ++){
84 _ang = e[i].k;
85 if(e[i].typ & 1){
86 dir = (Point) {cos(_ang), sin(_ang)};
87 if(s.empty() || sgn(abs(LineIntersection(*s.begin(), (Line) {ori, dir})) - abs(p[e[i].id] - p[x])) > 0){
88 cnt ++, rec[cnt] = e[i].id;
89 }
90 }
91 else if(!e[i].typ) s.insert(seg[e[i].id]);
92 else s.erase(seg[e[i].id]);
93 }
94
95 return cnt;
96 }
97
98 int Tcase;
99
100 char fi[100] = "pcx.in", fo[100] = "pcx.ans";
101 void Solve(){
102 printf("Case #%d:\n", ++ Tcase);
103 double x, y;
104 Point a, b;
105 for(int i = 1; i <= n; i ++){
106 scanf("%lf%lf", &x, &y);
107 p[i] = (Point) {x, y};
108 }
109 for(int i = 1; i <= m; i ++){
110 scanf("%lf%lf", &x, &y);
111 a = (Point) {x, y};
112 scanf("%lf%lf", &x, &y);
113 b = (Point) {x, y};
114 w[i] = (Line) {a, b};
115 }
116
117 int ans;
118 for(int i = 1; i <= q; i ++){
119 scanf("%lf%lf", &x, &y);
120 p[n + 1] = (Point) {x, y};
121 ans = Calc(n + 1);
122 printf("%d\n", ans);
123 }
124
125 return;
126 }
127
128 int main(){
129 // freopen("_pc.in", "r", stdin);
130 // freopen("_pc.ans", "w", stdout);
131 while(~scanf("%d%d%d", &n, &m, &q))
132 Solve();
133 //printf("--->%lf\n", (double) clock() / CLOCKS_PER_SEC);
134 return 0;
135 }