Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #define _CRT_SECURE_NO_WARNINGS
- #include <iostream>
- #include <fstream>
- #include <string>
- #include <vector>
- #include <cmath>
- #include <set>
- #include <map>
- #include <algorithm>
- #include <iomanip>
- using namespace std;
- #define ll long long
- const ll INF = 999999999999;
- void solve();
- void test();
- int main() {
- ios::sync_with_stdio(0);
- cin.tie(0);
- cout.tie(0);
- cout << fixed;
- cout << setprecision(15);
- #ifdef _DEBUG
- freopen("input.txt", "r", stdin);
- #endif
- solve();
- //test();
- return 0;
- }
- struct Point {
- ll x, y;
- Point(ll _x, ll _y) {
- y = _y;
- x = _x;
- }
- Point() {}
- };
- struct GeometricVector {
- ll x, y;
- GeometricVector(Point b, Point e) {
- x = e.x - b.x;
- y = e.y - b.y;
- }
- GeometricVector() {}
- ll operator *(GeometricVector A) {
- return x * A.y - y * A.x;
- }
- };
- ll takeArea(vector<Point>v) {
- ll res = 0;
- for (auto i = 0; i < v.size(); i++) {
- if (i != v.size() - 1) {
- GeometricVector f(Point(0, 0), v[i]);
- GeometricVector s(Point(0, 0), v[i + 1]);
- res += f * s;
- }
- else {
- GeometricVector f(Point(0, 0), v[i]);
- GeometricVector s(Point(0, 0), v[0]);
- res += f * s;
- }
- }
- //res /= 2;
- res = abs(res);
- return res;
- }
- vector<Point>polygon;
- void solve() {
- ll n;
- cin >> n;
- polygon.resize(n);
- for (int i = 0; i < n; i++) {
- cin >> polygon[i].x >> polygon[i].y;
- }
- ll area = (takeArea(polygon));
- pair<ll, ll>ans;
- ll k = INF;
- for (int i = 0; i < n; i++) {
- ll check = 0;
- ll last;
- for (int j = i + 2; true; j++) {
- last = j - 1;
- if (j >= n) j = j - n;
- if (last < 0) last = n + last;
- if (last == 6) last = 0;
- if (j == i) break;
- vector<Point>now = { polygon[i],polygon[last],polygon[j] };
- check += takeArea(now);
- //last++;
- //if (last >= n) last = last - n;
- if (abs(area - 2 * check) < k) {
- ans.first = i;
- ans.second = j;
- k = abs(area - 2 * check);
- }
- }
- }
- cout << ans.first + 1 << ' ' << ans.second + 1;
- }
- void test() {
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement