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 118 119 120 121 122 123 124 125 126 127
| #include <bits/stdc++.h> using namespace std; typedef long long ll; typedef double db; const db eps = 1e-10; const db pi = acos(-1.0); const ll maxn = 5010;
inline int dcmp(db x) { if(fabs(x) < eps) return 0; return x > 0? 1: -1; }
class Point { public: double x, y; Point(double x = 0, double y = 0) : x(x), y(y) {}
void input() { scanf("%lf%lf", &x, &y); }
bool operator<(const Point &a) const { return (!dcmp(x - a.x))? dcmp(y - a.y) < 0: x < a.x; }
bool operator==(const Point &a) const { return dcmp(x - a.x) == 0 && dcmp(y - a.y) == 0; }
db dis2(const Point a) { return pow(x - a.x, 2) + pow(y - a.y, 2); }
db dis(const Point a) { return sqrt(dis2(a)); }
db dis2() { return x * x + y * y; }
db dis() { return sqrt(dis2()); }
Point operator+(const Point a) { return Point(x + a.x, y + a.y); }
Point operator-(const Point a) { return Point(x - a.x, y - a.y); }
Point operator*(double p) { return Point(x * p, y * p); }
Point operator/(double p) { return Point(x / p, y / p); }
db dot(const Point a) { return x * a.x + y * a.y; }
db cross(const Point a) { return x * a.y - y * a.x; } };
db area(Point A, Point B, Point C) { return abs((A - B).cross(A - C)); }
typedef vector<Point> Polygon; Polygon Andrew(vector<Point> p) { int n = p.size(), cnt = 0; Polygon ans(2 * n); sort(p.begin(), p.end()); for (int i = 0; i < n; ++i) { while (cnt >= 2 && (ans[cnt - 1] - ans[cnt - 2]).cross(p[i] - ans[cnt - 2]) < eps) { --cnt; } ans[cnt++] = p[i]; } int t = cnt + 1; for (int i = n - 1; i > 0; --i) { while (cnt >= t && (ans[cnt - 1] - ans[cnt - 2]).cross(p[i - 1] - ans[cnt - 2]) < eps) { --cnt; } ans[cnt++] = p[i - 1]; } ans.resize(cnt - 1); return ans; }
vector<Point> p;
int main() { int n; scanf("%d", &n); for(int i = 0; i < n; ++i) { Point tmp; tmp.input(); p.push_back(tmp); } p = Andrew(p); n = p.size(); db ans = 0.0; if(n < 3) { printf("%.5lf\n", ans); return 0; } for(int i = 0; i < n; ++i) { int k = i + 2; for(int j = i + 1; j < n; ++j) { while(k + 1 < n && area(p[i], p[j], p[k]) < area(p[i], p[j], p[k + 1])) { ++k; } ans = max(ans, area(p[i], p[j], p[k])); } } printf("%.5lf\n", ans * 0.5); return 0; }
|