Submission #996940

#	Time	Username	Problem	Language	Result	Execution time	Memory
996940		Lucpp	Portal (BOI24_portal)	C++17	100 / 100	21 ms	4348 KiB

Main

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

tuple<ll, ll, ll> euclid(ll a, ll b){
	if(b == 0) return {a, 1, 0};
	ll q = a/b;
	auto [g, s, t] = euclid(b, a - q*b);
	return {g, t, s - q*t};
}

int main() {
	cin.tie(0)->sync_with_stdio(false);
	int n;
	cin >> n;
	vector<ll> x(n), y(n);
	for(int i = 0; i < n; i++) cin >> x[i] >> y[i];
	if(n <= 2){
		cout << "-1\n";
		return 0;
	}
	vector<vector<ll>> a(2, vector<ll>(n-1));
	for(int i = 0; i < n-1; i++){
		a[0][i] = x[i+1] - x[0];
		a[1][i] = y[i+1] - y[0];
	}
	for(int i = 0; i < n-1; i++){
		if(a[0][i] != 0){
			swap(a[0][0], a[0][i]);
			swap(a[1][0], a[1][i]);
			break;
		}
	}
	if(a[0][0] == 0){
		cout << "-1\n";
		return 0;
	}
	ll ans = 0;
	for(int i = 1; i < n-1; i++){
		auto [g, s, t] = euclid(a[0][0], a[0][i]);
		ll a00 = a[0][0] * s + a[0][i] * t;
		ll a10 = a[1][0] * s + a[1][i] * t;
		ll a0i = 0;
		ll a1i = a[1][0] * (-a[0][i]/g) + a[1][i] * (a[0][0] / g);
		if(ans != 0) a10 %= ans;
		a[0][0] = a00;
		a[1][0] = a10;
		a[0][i] = a0i;
		a[1][i] = a1i;
		ans = gcd(ans, a[1][i]);
	}
	if(ans == 0) cout << "-1\n";
	else cout << abs(ans * a[0][0]) << "\n";
}

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