Submission #1050984

#	Time	Username	Problem	Language	Result	Execution time	Memory
1050984		GusterGoose27	Portal (BOI24_portal)	C++17	100 / 100	18 ms	1884 KiB

Main

#include <bits/stdc++.h>

#define sz(s) (int)s.size()

using namespace std;

const int MAXN = 1e5+5;

typedef long long ll;
typedef array<ll, 2> pt;

ll operator*(pt a, pt b) {
	return a[0]*b[1] - a[1]*b[0];
}

ll dot(pt a, pt b) {
	return a[0]*b[0] + a[1]*b[1];
}

pt operator*(ll a, pt b) {
	return {a*b[0], a*b[1]};
}

pt operator/(pt a, ll b) {
	return {a[0]/b,a[1]/b};
}

pt operator+(pt a, pt b) {
	return {a[0]+b[0], a[1]+b[1]};
}

pt operator-(pt a, pt b) {
	return {a[0]-b[0], a[1]-b[1]};
}

ll _abs(ll a) {
	return a < 0 ? -a : a;
}

ll l1(pt a) {
	return _abs(a[0]) + _abs(a[1]);
}

ll _gcd(ll a, ll b) {
	a = _abs(a);
	b = _abs(b);
	assert(a+b);
	int shift = 0;
	while (a && b) {
		if (!(a&1) && !(b&1)) {
			shift++;
			a >>= 1; b >>= 1;
			continue;
		}
		if (!(a&1)) {
			a >>= 1;
			continue;
		}
		if (!(b&1)) {
			b >>= 1;
			continue;
		}
		if (a > b) a = (a-b)/2;
		else b = (b-a)/2;
	}
	return (a+b) << shift;
}

struct cmp {
	bool operator()(pt a, pt b) {
		int d = l1(a)-l1(b);
		return d == 0 ? (a < b) : (d < 0);
	}
} cmp;

ll round_to(ll a, ll b) {
	if (a < 0) return -round_to(-a, b);
	return a / b + ((a % b)*2 >= b);
}

pt proj(pt c, pt a, pt b) {
	ll dem = a*b;
	ll num1 = c*b;
	ll num2 = a*c;
	if (dem < 0) {
		num1 *= -1;
		num2 *= -1;
		dem *= -1;
	}
	num1 = round_to(num1, dem);
	num2 = round_to(num2, dem);
	return c - (num1*a + num2*b);
}

pt reduce_two(pt a, pt b) {
	assert(a*b == 0);
	ll g = _gcd(l1(a), l1(b));
	ll m = l1(a)/g;
	return a / m;
}

void reduce(vector<pt> &basis) {
	if (sz(basis) == 1) return;
	else if (sz(basis) == 2) {
		if (basis[0]*basis[1] == 0) {
			basis[0] = reduce_two(basis[0], basis[1]);
			basis.pop_back();
			// ll g = _gcd(l1(basis[0]), l1(basis[1]));
			// ll m = l1(basis[0])/g;
			// basis[0][0] /= m;
			// basis[0][1] /= m;
			// basis.pop_back();
		}
		else return;
	}
	else {
		assert(sz(basis) == 3);
		sort(basis.begin(), basis.end(), cmp);
		for (int i = 2; i >= 0; i--) {
			pt a = basis[i == 0];
			pt b = basis[1 + (i <= 1)];
			if (a*b == 0) {
				pt n1 = reduce_two(a, b);
				pt c = basis[i];
				basis[0] = n1;
				basis[1] = c;
				basis.pop_back();
				return reduce(basis);
			}
			pt c = basis[i];
			pt res = proj(c, a, b);
			if (l1(res) < l1(c)) {
				if (l1(res) == 0) {
					basis[0] = a;
					basis[1] = b;
					basis.pop_back();
				}
				else basis[i] = res;
				return reduce(basis);
			}
		}
		assert(false);
	}
}

void read(pt &p) {
	cin >> p[0] >> p[1];
}

int main() {
	ios_base::sync_with_stdio(false); cin.tie(NULL);
	int n; cin >> n;
	pt p; read(p);
	n--;
	vector<pt> basis;
	for (int i = 0; i < n; i++) {
		pt v; read(v);
		basis.push_back(v-p);
		reduce(basis);
		p = v;
	}
	if (sz(basis) <= 1) cout << "-1\n";
	else cout << _abs(basis[0]*basis[1]) << '\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