Advertisement
Guest User

Untitled

a guest
Apr 20th, 2018
50
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.96 KB | None | 0 0
  1. #define _CRT_SECURE_NO_WARNINGS
  2. #include <iostream>
  3. #include <fstream>
  4. #include <string>
  5. #include <vector>
  6. #include <cmath>
  7. #include <set>
  8. #include <map>
  9. #include <algorithm>
  10. #include <iomanip>
  11. using namespace std;
  12. #define ll long long
  13. const ll INF = 999999999999;
  14. void solve();
  15. void test();
  16. int main() {
  17.     ios::sync_with_stdio(0);
  18.     cin.tie(0);
  19.     cout.tie(0);
  20.     cout << fixed;
  21.     cout << setprecision(15);
  22. #ifdef _DEBUG
  23.     freopen("input.txt", "r", stdin);
  24. #endif
  25.     solve();
  26.     //test();
  27.     return 0;
  28. }
  29. struct Point {
  30.     ll x, y;
  31.     Point(ll _x, ll _y) {
  32.         y = _y;
  33.         x = _x;
  34.     }
  35.     Point() {}
  36. };
  37. struct GeometricVector {
  38.     ll x, y;
  39.     GeometricVector(Point b, Point e) {
  40.         x = e.x - b.x;
  41.         y = e.y - b.y;
  42.     }
  43.     GeometricVector() {}
  44.     ll operator *(GeometricVector A) {
  45.         return x * A.y - y * A.x;
  46.     }
  47. };
  48. ll takeArea(vector<Point>v) {
  49.     ll res = 0;
  50.     for (auto i = 0; i < v.size(); i++) {
  51.         if (i != v.size() - 1) {
  52.             GeometricVector f(Point(0, 0), v[i]);
  53.             GeometricVector s(Point(0, 0), v[i + 1]);
  54.             res += f * s;
  55.         }
  56.         else {
  57.             GeometricVector f(Point(0, 0), v[i]);
  58.             GeometricVector s(Point(0, 0), v[0]);
  59.             res += f * s;
  60.         }
  61.     }
  62.     //res /= 2;
  63.     res = abs(res);
  64.     return res;
  65. }
  66. vector<Point>polygon;
  67. void solve() {
  68.     ll n;
  69.     cin >> n;
  70.     polygon.resize(n);
  71.     for (int i = 0; i < n; i++) {
  72.         cin >> polygon[i].x >> polygon[i].y;
  73.     }
  74.     ll area = (takeArea(polygon));
  75.     pair<ll, ll>ans;
  76.     ll k = INF;
  77.     for (int i = 0; i < n; i++) {
  78.         ll check = 0;
  79.         ll last;
  80.         for (int j = i + 2; true; j++) {
  81.             last = j - 1;
  82.             if (j >= n) j = j - n;
  83.             if (last < 0) last = n + last;
  84.             if (last == 6) last = 0;
  85.             if (j == i) break;
  86.             vector<Point>now = { polygon[i],polygon[last],polygon[j] };
  87.             check += takeArea(now);
  88.             //last++;
  89.             //if (last >= n) last = last - n;
  90.             if (abs(area - 2 * check) < k) {
  91.                 ans.first = i;
  92.                 ans.second = j;
  93.                 k = abs(area - 2 * check);
  94.             }
  95.         }
  96.     }
  97.     cout << ans.first + 1 << ' ' << ans.second + 1;
  98. }
  99. void test() {
  100. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement