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
| #include <cstdio>
#include <cmath>
#include <algorithm>
const int MAXN = 2005;
const double EPS = 1e-9;
int dcmp(double x) {
if (fabs(x) <= EPS) return 0;
if (x > EPS) return 1;
else return -1;
}
struct Point {
double x, y;
Point(double x = 0, double y = 0) : x(x), y(y) {}
bool operator<(const Point &another) const {
return x < another.x || (x == another.x && y < another.y);
}
bool operator==(const Point &another) const {
return !dcmp(x - another.x) && !dcmp(y - another.y);
}
friend Point operator-(const Point &a, const Point &b) {
return Point(a.x - b.x, a.y - b.y);
}
friend double cross(const Point &a, const Point &b) {
return a.x * b.y - a.y * b.x;
}
} P[MAXN], ch[MAXN];
int getConvexHell(int n) {
std::sort(P, P + n);
int m = 0;
for (int i = 0; i < n; i++) {
while (m > 1 && cross(ch[m - 1] - ch[m - 2], P[i] - ch[m - 2]) <= 0) m--;
ch[m++] = P[i];
}
int k = m;
for (int i = n - 1; ~i; i--) {
while (m > k && cross(ch[m - 1] - ch[m - 2], P[i] - ch[m - 2]) <= 0) m--;
ch[m++] = P[i];
}
m > 1 ? m-- : 0;
return m;
}
double rotatingCalipers(int n) {
double ans = 0;
for (int curr = 0; curr < n; curr++) {
int left = (curr + 2) % n, right = (curr + 1) % n;
for (int up = (curr + 1) % n; up < n; up++) {
Point currV = ch[up] - ch[curr];
while ((right + 1) % n != up && cross(ch[right + 1] - ch[curr], currV) > cross(ch[right] - ch[curr], currV))
right = (right + 1) % n;
while ((left + 1) % n != curr && cross(currV, ch[left + 1] - ch[curr]) > cross(currV, ch[left] - ch[curr]))
left = (left + 1) % n;
ans = std::max(ans, cross(ch[right] - ch[curr], currV) + cross(currV, ch[left] - ch[curr]));
}
}
return ans;
}
void calcTriangle(int n) {
static bool onConvexHell[MAXN];
for (int i = 0; i < n; i++)
onConvexHell[i] = (P[i] == ch[0] || P[i] == ch[1] || P[i] == ch[2]);
double trianArea = cross(ch[1] - ch[0], ch[2] - ch[0]), ans = 0;
for (int i = 0; i < n; i++) if (!onConvexHell[i]) {
double temp = std::min(std::min(cross(ch[0] - P[i], ch[1] - P[i]), cross(ch[1] - P[i], ch[2] - P[i])),
cross(ch[2] - P[i], ch[0] - P[i]));
ans = std::max(ans, trianArea - temp);
}
printf("%.3lf\n", ans / 2);
}
int main() {
int n;
scanf("%d", &n);
for (int i = 0; i < n; i++) scanf("%lf %lf", &P[i].x, &P[i].y);
int m = getConvexHell(n);
if (m == 3) calcTriangle(n);
else printf("%.3lf\n", rotatingCalipers(m) / 2);
return 0;
}
|