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 -21  
Sample Output
Case #1: 2 Case #2: 3 2  
Source
分析:
平面上有一些点和一些线段,保证这些线段互不相交,点不在线段上。
每次问从一个点能看到多少个点。一个点能看到另一点当且仅当这两点连线的线段不和任何一个已知的线段相交。(这里的相交均指非规范相交)
每次以询问点为极点极角排序。线段两端点拆成两个事件,一次出现,一次消失。对于枚举的某一个角度,能否看见当前角度的点仅取决于当前角度上离极点最近的线段,由于保证线段不相交,一条线段在插入时和还存在线段的相对位置是不会改变的,所以可以用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 }
 
posted @ 2017-09-02 17:56 Angel_Kitty 阅读(...) 评论(...) 编辑 收藏
ACM竞赛&数学建模竞赛 - 创建于 2017年2月2日 这是一位ACM爱好者&数学爱好者的个人站,内容主要是算法&数据结构&数学研究的技术文章,大部分来自学习,部分来源于网络,希望对大家有所帮助。 致力于ACM算法研究工作,喜爱交友,关注互联网前沿技术与趋势。
Font Awesome | Respond.js | Bootstrap中文网