雷达安装
poj1328
以岛屿为圆心，雷达范围为半径，计算此圆与x轴交点的线段，以此把所有岛屿的区间计算出来。
因此，这道题就变成了在数轴上选最少的点，覆盖给定线段。
把每条线段以右端点排序，然后进行选择即可。
sqrt函数使用时要保证数据类型一致。
注意输出格式以及Case的C要大写= =
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
| #include "stdafx.h"
#include <iostream>
#include <algorithm>
#include <cmath>
using namespace std;
struct radarRange {
double left;
double right;
bool operator < (const radarRange &x) const
{
if (right != x.right) return right < x.right;
return left < x.left;
}
};
struct islandPosition {
int x;
int y;
};
int radar()
{
int n, d;
cin >> n >> d;
if (n == 0 && d == 0)
return -2;
islandPosition *p = new islandPosition[n];
radarRange *r = new radarRange[n];
for (int i = 0; i < n; i++)
{
cin >> p[i].x >> p[i].y;
}
if (d == 0)
return -1;
for (int i = 0; i < n; i++)
if (p[i].y > d)
{
return -1;
}
for (int i = 0; i < n; i++)
{
double tmp = sqrt(double(d *d) - double(p[i].y * p[i].y));
r[i].left = p[i].x - tmp;
r[i].right = p[i].x + tmp;
}
sort(r, r + n);
double start, end;
int sum = 1;
start = r[0].left;
end = r[0].right;
for (int i = 1; i < n; i++)
{
if (r[i].left <= end && r[i].left >= start)
{
start = r[i].left;
}
if (r[i].left > end)
{
start = r[i].left;
end = r[i].right;
sum++;
}
}
delete[] p; delete[] r;
return sum;
}
int main()
{
int tmp;
int sum = 1;
while (1)
{
tmp = radar();
if (tmp == -2) break;
cout << "Case " << sum++ << ": " << tmp << endl;
}
system("pause");
}
|