Advertisement
Guest User

Untitled

a guest
Apr 16th, 2018
84
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.49 KB | None | 0 0
  1. #include <iostream>
  2. #include <vector>
  3. #include <cstdio>
  4. #include <set>
  5. #include <cassert>
  6. #include <map>
  7. #include <algorithm>
  8.  
  9. using namespace std;
  10.  
  11. struct Point {
  12.     int x, y;
  13.     Point(int x = 0, int y = 0):
  14.         x(x), y(y) {}
  15. };
  16.  
  17. struct Vector {
  18.     int x, y;
  19.     Vector(int x = 0, int y = 0):
  20.         x(x), y(y) {}
  21.     Vector(Point a, Point b):
  22.         x(b.x - a.x), y(b.y - a.y) {}
  23. };
  24.  
  25. long long operator ^(Vector v1, Vector v2) { return v1.x * v2.y - v1.y * v2.x; }
  26.  
  27. vector <Point> a;
  28.  
  29. int main() {
  30.     assert(freopen("input.txt", "r", stdin));
  31.     //assert(freopen("output.txt", "w", stdout));
  32.    
  33.     ios_base::sync_with_stdio(false);
  34.    
  35.     int n; cin >> n;
  36.     a.resize(n);
  37.     for (int i = 0; i < n; i++)
  38.         cin >> a[i].x >> a[i].y;
  39.    
  40.     long long s = 0;
  41.     for (int i = 1; i < n - 1; i++)
  42.         s += (Vector(a[0], a[i]) ^ Vector(a[0], a[i + 1]));
  43.    
  44.     long long maxres = -1;
  45.     int resi = -1, resj = -1;
  46.     for (int i = 0; i < n; i++) {
  47.         long long cur_s = 0;
  48.         int p = i + 1;
  49.         while (true) {
  50.             int nxtp = (p + 1) % n;
  51.             cur_s += Vector(a[i], a[p]) ^ Vector(a[i], a[nxtp]);
  52.             if (2 * abs(cur_s) > abs(s))
  53.                 break;
  54.             p = nxtp;
  55.         }
  56.        
  57.         if (abs(cur_s) > maxres) {
  58.             maxres = abs(cur_s);
  59.             resi = i, resj = p;
  60.         }
  61.         int nxtp = (p + 1) % n;
  62.         cur_s += Vector(a[i], a[p]) ^ Vector(a[i], a[nxtp]);
  63.         p = nxtp;
  64.         if (min(abs(cur_s), abs(s - cur_s)) > maxres) {
  65.             maxres = min(abs(cur_s), abs(s - cur_s));
  66.             resi = i, resj = p;
  67.         }
  68.     }
  69.    
  70.     cout << resi + 1 << " " << resj + 1 << endl;
  71.    
  72.     return 0;
  73. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement