UVa 1312 - Cricket Field

链接

传送门

题意

给出矩形中的$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
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int maxn = 110;
int y[maxn];
struct point {
int x, y;
bool operator < (const point& rhs) const {
return x < rhs.x;
}
} p[maxn];
int main() {
int t;
scanf("%d", &t);
while (t--) {
int n, w, h;
scanf("%d%d%d", &n, &w, &h);
int cnt = 2;
y[0] = 0, y[1] = h;
for (int i = 0; i < n; ++i) {
scanf("%d%d", &p[i].x, &p[i].y);
y[cnt++] = p[i].y;
}
sort(p, p + n);
sort(y, y + cnt);
p[n++].x = w;
cnt = int(unique(y, y + cnt) - y);
int len = 0, ansx = 0, ansy = 0;
for (int i = 0; i < cnt; ++i) {
for (int j = i + 1; j < cnt; ++j) {
int x = 0, pre = 0, l = 0;
for (int k = 0; k < n; ++k) {
if (k == n - 1 || (p[k].y > y[i] && p[k].y < y[j])) {
if (p[k].x - pre > l) {
l = p[k].x - pre;
x = pre;
}
pre = p[k].x;
}
}
l = min(l, y[j] - y[i]);
if (l > len) {
ansx = x;
ansy = y[i];
len = l;
}
}
}
printf("%d %d %d\n", ansx, ansy, len);
if (t) {
puts("");
}
}
return 0;
}