Submission #994694

#	Time	Username	Problem	Language	Result	Execution time	Memory
994694		pavement	Portal (BOI24_portal)	C++17	100 / 100	52 ms	6740 KiB

Main

#include <bits/stdc++.h>
using namespace std;

#define pb push_back
#define eb emplace_back
#define int __int128

using ii = pair<int, int>;
using ll = long long;

int N, x[100005], y[100005], dx[100005], dy[100005];
ll _N, _x, _y;

vector<ii> reduce(vector<ii> v) {
	//~ cout << "BEF\n";
	//~ for (auto [x, y] : v) {
		//~ cout << x << ' ' << y << '\n';
	//~ }
	for (int rep = 0; rep < 2; rep++) {
		// reduce 0 and 1
		while (v[0].first && v[1].first) {
			if (v[0].first < 0) {
				v[0].first = -v[0].first;
				v[0].second = -v[0].second;
			}
			if (v[1].first < 0) {
				v[1].first = -v[1].first;
				v[1].second = -v[1].second;
			}
			if (v[1].first > v[0].first) {
				swap(v[0], v[1]);
			}
			int t = v[0].first / v[1].first;
			v[0].first -= t * v[1].first;
			v[0].second -= t * v[1].second;
		}
		if (v[0].first == 0) {
			swap(v[0], v[2]);
		} else {
			swap(v[1], v[2]);
		}
	}
	//~ cout << "AFT\n";
	//~ for (auto [x, y] : v) {
		//~ cout << x << ' ' << y << '\n';
	//~ }
	vector<int> zz;
	vector<ii> oth;
	for (int i = 0; i < 3; i++) {
		if (v[i].first == 0) {
			zz.pb(v[i].second);
		} else {
			oth.pb(v[i]);
		}
	}
	assert(zz.size() >= 2);
	int g = 0;
	for (auto i : zz) {
		g = __gcd(g, i);
	}
	oth.eb(0, g);
	return oth;
}

main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin >> _N;
	N = _N;
	for (int i = 1; i <= N; i++) {
		cin >> _x >> _y;
		x[i] = _x;
		y[i] = _y;
	}
	vector<ii> vec;
	for (int i = 1; i < N; i++) {
		dx[i] = x[i + 1] - x[i];
		dy[i] = y[i + 1] - y[i];
		if ((int)vec.size() < 3) {
			vec.eb(dx[i], dy[i]);
		}
		if ((int)vec.size() == 3) {
			vec = reduce(vec);
		}
	}
	assert(vec.size() <= 2);
	if (vec.size() <= 1) {
		cout << "-1\n";
	} else {
		if (vec[0].first * vec[1].second == vec[0].second * vec[1].first) {
			cout << "-1\n";
		} else {
			cout << llabs(vec[0].first * vec[1].second - vec[0].second * vec[1].first) << '\n';
		}
	}
}

Compilation message (stderr)

Main.cpp:65:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   65 | main() {
      | ^~~~

• Subtask 1: 1 / 1
• Subtask 2: 10 / 10
• Subtask 3: 10 / 10
• Subtask 4: 29 / 29
• Subtask 5: 15 / 15
• Subtask 6: 35 / 35