Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #define _CRT_SECURE_NO_WARNINGS
- #include <iostream>
- #include <cstdio>
- #include <algorithm>
- #include <cstdlib>
- #include <cmath>
- #include <vector>
- #include <map>
- #include <set>
- #include <queue>
- #include <string>
- #include <cstring>
- #include <cassert>
- #include <ctime>
- using namespace std;
- struct Point
- {
- long long x, y;
- Point() : x(), y() {}
- Point(long long _x, long long _y) : x(_x), y(_y) {}
- void scan()
- {
- scanf("%lf%lf", &x, &y);
- }
- Point operator + (Point p)
- {
- return Point(x + p.x, y + p.y);
- }
- Point operator - (Point p)
- {
- return Point(x - p.x, y - p.y);
- }
- long long operator * (Point p)
- {
- return x * p.y - y * p.x;
- }
- };
- long long get_area(Point A, Point B, Point C)
- {
- return abs((B - A) * (C - A));
- }
- const int N = 5005;
- struct Triple
- {
- int a, b, c;
- Triple() : a(), b(), c() {}
- Triple(int _a, int _b, int _c) : a(_a), b(_b), c(_c) {}
- };
- int n;
- Point points[N];
- long long dp[N][N];
- Triple par[N][N];
- long long get_area(int i, int j, int k)
- {
- return get_area(points[i], points[j], points[k]);
- }
- void solve()
- {
- scanf("%d", &n);
- for (int i = 0; i < n; i++)
- points[i].scan();
- for (int i = 0; i < n; i++)
- {
- int j = (i + 2) % n;
- int k = (i + 1) % n;
- long long s = get_area(i, j, k);
- for (int it1 = 0; it1 < n - 1; it1++)
- {
- while (true)
- {
- int new_k = (k + 1) % n;
- long long new_s = get_area(i, j, new_k);
- if (new_s < s)
- break;
- k = new_k;
- s = new_s;
- }
- dp[i][j] = dp[i][(j - 1 + n) % n];
- par[i][j] = par[i][(j - 1 + n) % n];
- if (s > dp[i][j])
- {
- dp[i][j] = s;
- par[i][j] = Triple(i, j, k);
- }
- j = (j + 1) % n;
- }
- }
- long long best_ans = -1;
- Triple best_min, best_max;
- for (int i = 0; i < n; i++)
- {
- int j = (i + 2) % n;
- long long val = dp[j][i];
- val -= get_area(i, (i + 1) % n, (i + 2) % n);
- if (val > best_ans)
- {
- best_ans = val;
- best_min = Triple(i, (i + 1) % n, (i + 2) % n);
- best_max = par[j][i];
- }
- }
- printf("%.1lf\n", best_ans / 2.0);
- best_min.print();
- }
- int main()
- {
- freopen(".in", "r", stdin);
- freopen(".out", "w", stdout);
- solve();
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement