UVaLive 6675 - Easy Geometry

链接

传送门

题意

如图,给出在格点上的凸多边形,输出面积最大的边与坐标轴平行的矩形的面积。

思路

首先,最大矩形的面积为矩形宽度的上凸函数。然后,对于指定宽度的矩形,矩形的面积为左边界的位置的上凸函数。给出指定的位置可以求出当前位置与多边形交点的$y$值。因此可以使用三分套三分套二分的方式解决这道题。

UVa 1679 - Easy Geometry和这个是同一道题,不过好像题的数据有问题,NEERC官方题解中tourist的代码也过不了。

代码

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
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
using namespace std;
const int inf = 0x3f3f3f3f;
const int maxn = 100010;
const int maxt = 50;
int n, uNum, dNum;
int x[maxn], y[maxn];
double ans, h;
double Min, Max;
double tmpya, tmpyb;
double xa, xb, ya, yb;
double ux[maxn], uy[maxn];
double dx[maxn], dy[maxn];
double calY(double* vx, double* vy, int num, double x) {
int p = int(upper_bound(vx, vx + num, x) - vx);
return vy[p - 1] + (vy[p] - vy[p - 1]) / (vx[p] - vx[p - 1]) * (x - vx[p - 1]);
}
double calH(double x, double w) {
tmpya = max(calY(dx, dy, dNum, x), calY(dx, dy, dNum, x + w));
tmpyb = min(calY(ux, uy, uNum, x), calY(ux, uy, uNum, x + w));
double h = tmpyb - tmpya;
return h > 0 ? h : 0;
}
double calS(double w) {
double lx = Min, rx = Max - w;
for (int i = 0; i < maxt; ++i) {
double xx1 = (lx * 2 + rx) / 3;
double xx2 = (lx + rx * 2) / 3;
double s = calH(xx2, w);
if (s == 0.0 || s < calH(xx1, w)) {
rx = xx2;
} else {
lx = xx1;
}
}
double res = calH((lx + rx) / 2, w) * w;
if (res > ans) {
ans = res;
xa = (lx + rx) / 2;
xb = xa + w;
ya = tmpya;
yb = tmpyb;
}
return res;
}
void gen(double* vx, double* vy, int& num, int p, int d, int k) {
while (x[(p + n + d) % n] == Min) {
p = (p + n + d) % n;
}
for (num = 0;;) {
vx[num] = x[p];
vy[num] = y[p];
++num;
if (x[p] == Max) {
return;
}
p += d;
if (p == k) {
p = (p + n) % n;
}
}
}
int main() {
while (~scanf("%d", &n)) {
Min = inf, Max = -inf;
int p = 0;
for (int i = 0; i < n; ++i) {
scanf("%d%d", &x[i], &y[i]);
if (x[i] < x[p]) {
p = i;
}
Min = min(Min, double(x[i]));
Max = max(Max, double(x[i]));
}
gen(ux, uy, uNum, p, 1, n);
gen(dx, dy, dNum, p, -1, -1);
double lw = 0, rw = Max - Min;
ans = 0;
for (int i = 0; i < maxt; ++i) {
double w1 = (lw * 2 + rw) / 3;
double w2 = (lw + rw * 2) / 3;
double s = calS(w2);
if (s == 0.0 || s < calS(w1)) {
rw = w2;
} else {
lw = w1;
}
}
printf("%.10f %.10f %.10f %.10f\n", xa, ya, xb, yb);
}
return 0;
}

支付宝扫码领红包