Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <vector>
- #include <cstdio>
- #include <set>
- #include <cassert>
- #include <map>
- #include <algorithm>
- using namespace std;
- struct Point {
- int x, y;
- Point(int x = 0, int y = 0):
- x(x), y(y) {}
- };
- struct Vector {
- int x, y;
- Vector(int x = 0, int y = 0):
- x(x), y(y) {}
- Vector(Point a, Point b):
- x(b.x - a.x), y(b.y - a.y) {}
- };
- long long operator ^(Vector v1, Vector v2) { return v1.x * v2.y - v1.y * v2.x; }
- vector <Point> a;
- int main() {
- assert(freopen("input.txt", "r", stdin));
- //assert(freopen("output.txt", "w", stdout));
- ios_base::sync_with_stdio(false);
- int n; cin >> n;
- a.resize(n);
- for (int i = 0; i < n; i++)
- cin >> a[i].x >> a[i].y;
- long long s = 0;
- for (int i = 1; i < n - 1; i++)
- s += (Vector(a[0], a[i]) ^ Vector(a[0], a[i + 1]));
- long long maxres = -1;
- int resi = -1, resj = -1;
- for (int i = 0; i < n; i++) {
- long long cur_s = 0;
- int p = i + 1;
- while (true) {
- int nxtp = (p + 1) % n;
- cur_s += Vector(a[i], a[p]) ^ Vector(a[i], a[nxtp]);
- if (2 * abs(cur_s) > abs(s))
- break;
- p = nxtp;
- }
- if (abs(cur_s) > maxres) {
- maxres = abs(cur_s);
- resi = i, resj = p;
- }
- int nxtp = (p + 1) % n;
- cur_s += Vector(a[i], a[p]) ^ Vector(a[i], a[nxtp]);
- p = nxtp;
- if (min(abs(cur_s), abs(s - cur_s)) > maxres) {
- maxres = min(abs(cur_s), abs(s - cur_s));
- resi = i, resj = p;
- }
- }
- cout << resi + 1 << " " << resj + 1 << endl;
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement