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; }
|