Advertisement
Guest User

Untitled

a guest
Nov 28th, 2014
136
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.19 KB | None | 0 0
  1. #define _CRT_SECURE_NO_WARNINGS
  2.  
  3. #include <iostream>
  4. #include <cstdio>
  5. #include <algorithm>
  6. #include <cstdlib>
  7. #include <cmath>
  8. #include <vector>
  9. #include <map>
  10. #include <set>
  11. #include <queue>
  12. #include <string>
  13. #include <cstring>
  14. #include <cassert>
  15. #include <ctime>
  16. using namespace std;
  17.  
  18. struct Point
  19. {
  20.     long long x, y;
  21.  
  22.     Point() : x(), y() {}
  23.  
  24.     Point(long long _x, long long _y) : x(_x), y(_y) {}
  25.  
  26.     void scan()
  27.     {
  28.         scanf("%lf%lf", &x, &y);
  29.     }
  30.  
  31.     Point operator + (Point p)
  32.     {
  33.         return Point(x + p.x, y + p.y);
  34.     }
  35.  
  36.     Point operator - (Point p)
  37.     {
  38.         return Point(x - p.x, y - p.y);
  39.     }
  40.  
  41.     long long operator * (Point p)
  42.     {
  43.         return x * p.y - y * p.x;
  44.     }
  45. };
  46.  
  47. long long get_area(Point A, Point B, Point C)
  48. {
  49.     return abs((B - A) * (C - A));
  50. }
  51.  
  52. const int N = 5005;
  53.  
  54. struct Triple
  55. {
  56.     int a, b, c;
  57.  
  58.     Triple() : a(), b(), c() {}
  59.  
  60.     Triple(int _a, int _b, int _c) : a(_a), b(_b), c(_c) {}
  61. };
  62.  
  63. int n;
  64. Point points[N];
  65. long long dp[N][N];
  66. Triple par[N][N];
  67.  
  68. long long get_area(int i, int j, int k)
  69. {
  70.     return get_area(points[i], points[j], points[k]);
  71. }
  72.  
  73. void solve()
  74. {
  75.     scanf("%d", &n);
  76.     for (int i = 0; i < n; i++)
  77.         points[i].scan();
  78.  
  79.     for (int i = 0; i < n; i++)
  80.     {
  81.         int j = (i + 2) % n;
  82.         int k = (i + 1) % n;
  83.         long long s = get_area(i, j, k);
  84.  
  85.         for (int it1 = 0; it1 < n - 1; it1++)
  86.         {
  87.             while (true)
  88.             {
  89.                 int new_k = (k + 1) % n;
  90.                 long long new_s = get_area(i, j, new_k);
  91.                 if (new_s < s)
  92.                     break;
  93.                 k = new_k;
  94.                 s = new_s;
  95.             }
  96.  
  97.             dp[i][j] = dp[i][(j - 1 + n) % n];
  98.             par[i][j] = par[i][(j - 1 + n) % n];
  99.  
  100.             if (s > dp[i][j])
  101.             {
  102.                 dp[i][j] = s;
  103.                 par[i][j] = Triple(i, j, k);
  104.             }
  105.  
  106.             j = (j + 1) % n;
  107.         }
  108.     }
  109.  
  110.     long long best_ans = -1;
  111.     Triple best_min, best_max;
  112.  
  113.     for (int i = 0; i < n; i++)
  114.     {
  115.         int j = (i + 2) % n;
  116.         long long val = dp[j][i];
  117.         val -= get_area(i, (i + 1) % n, (i + 2) % n);
  118.  
  119.         if (val > best_ans)
  120.         {
  121.             best_ans = val;
  122.             best_min = Triple(i, (i + 1) % n, (i + 2) % n);
  123.             best_max = par[j][i];
  124.         }
  125.     }
  126.  
  127.     printf("%.1lf\n", best_ans / 2.0);
  128.     best_min.print();
  129.  
  130. }
  131.  
  132. int main()
  133. {
  134.     freopen(".in", "r", stdin);
  135.     freopen(".out", "w", stdout);
  136.  
  137.     solve();
  138.  
  139.     return 0;
  140. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement