• API
• FAQ
• Tools
• Archive
daily pastebin goal
23%
SHARE
TWEET

# Untitled

a guest Apr 16th, 2018 49 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
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. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy.

Top