UVa 10535 - Shooter

链接

传送门

题意

给出$n$堵墙,用激光枪可以打穿一条直线上所有墙,给出所在的位置,输出最多一发打穿的墙的个数。

思路

预处理出每堵墙的射击范围,然后用扫描线求最大值。这道题貌似卡精度,题目中横纵坐标是等价的,求角度时调换参数就过不了了,略坑。

代码

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
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
#include <cmath>
using namespace std;
const int maxn = 510;
const double PI = acos(-1);
const double eps = 1e-8;
double ax[maxn], ay[maxn], bx[maxn], by[maxn];
struct range {
double ang;
int v;
bool operator < (const range& rhs) const {
if (fabs(ang - rhs.ang) > eps) {
return ang < rhs.ang;
} else {
return v > rhs.v;
}
}
} a[maxn << 1];
int main() {
int n;
while (~scanf("%d", &n) && n) {
for (int i = 0; i < n; ++i) {
scanf("%lf%lf%lf%lf", &ax[i], &ay[i], &bx[i], &by[i]);
}
double x, y;
int cnt = 0;
scanf("%lf%lf", &x, &y);
for (int i = 0; i < n; ++i) {
double l = atan2(ax[i] - x, ay[i] - y);
double r = atan2(bx[i] - x, by[i] - y);
if (l > r) {
swap(l, r);
}
if (r - l >= PI) {
a[cnt].ang = -PI, a[cnt].v = 1;
++cnt;
a[cnt].ang = l, a[cnt].v = -1;
++cnt;
l = r, r = PI;
}
a[cnt].ang = l, a[cnt].v = 1;
++cnt;
a[cnt].ang = r, a[cnt].v = -1;
++cnt;
}
sort(a, a + cnt);
int ans = 0, cur = 0;
for (int i = 0; i < cnt; ++i) {
cur += a[i].v;
ans = max(ans, cur);
}
printf("%d\n", ans);
}
return 0;
}

支付宝扫码领红包