Submission #1308342

#	Time	Username	Problem	Language	Result	Execution time	Memory
1308342		bornag	SIR (COI15_sir)	C++20	0 / 100	1095 ms	25632 KiB

sir

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

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vii;
typedef vector<ll> vll;
typedef vector<pii> vpii;
typedef vector<pll> vpll;

#define pb push_back
#define eb emplace_back
#define upb upper_bound
#define lpb lower_bound
#define ppb pop_back
#define X first
#define Y second
#define all(a) a.begin(), a.end()
#define len(a) (int) (a.size())

const ll MOD = 1e9 + 7;
const ll BASE = 32;
const int MAXN = 3e5 + 7;

int n, m;
pll A[MAXN];

ll ccw(pll a, pll b, pll c) {
	return min(1LL, max(-1LL, a.X * (b.Y - c.Y) + b.X * (c.Y - a.Y) + c.X * (a.Y - b.Y)));
}

ll arf(pll a, pll b, pll c) {
	return abs(a.X * (b.Y - c.Y) + b.X * (c.Y - a.Y) + c.X * (a.Y - b.Y));
}

vpll hullsort(vpll cords) {
	vpll lower, upper, ret;
	
	for(auto x : cords) {
		if(x != cords[0] && x != cords.back() && ccw(cords[0], cords.back(), x) >= 0) continue;
		while(lower.size() >= 2 && ccw(lower[lower.size() - 1], lower.back(), x) == 1)
			lower.ppb();
		lower.pb(x);
	}
	
	for(auto x : cords) {
		if(x != cords[0] && x != cords.back() && ccw(cords[0], cords.back(), x) < 0) continue;
		while(upper.size() >= 2 && ccw(upper[upper.size() - 1], upper.back(), x) == -1)
			upper.ppb();
		upper.pb(x);
	}
	
	upper.ppb();
	reverse(all(upper));
	upper.ppb();
	
	for(auto x : lower) ret.pb(x);
	for(auto x : upper) ret.pb(x);
	
	return ret;
}

void task() {
	cin >> n;
	
	for(int i = 0; i < n; i++)
		cin >> A[i].X >> A[i].Y;
		
	cin >> m;
	vpll cords(m);
	for(int i = 0; i < m; i++)
		cin >> cords[i].X >> cords[i].Y;
		
	vpll chull = hullsort(cords);
	m = len(chull);
	int holepoint = 0, secondpoint = 0;
	
	ll pov = 0, ans = 0;
	for(int i = 0; i < n; i++) {
		//od i - 1 do tu se pomicemo
		if(i > 0) pov -= arf(A[i - 1], A[i], A[secondpoint]);
		if(secondpoint < i) secondpoint = i, pov = 0;
		//sad pomicemo second point dok mozemo
		
		while(ccw(chull[holepoint], A[i], chull[(holepoint + 1) % m]) == 1)
			holepoint = (holepoint + 1) % m;
		//cout << "h" << holepoint << '\n';	
		
		while(ccw(chull[holepoint], A[i], A[(secondpoint + 1) % n]) == 1)
			pov += arf(A[i], A[secondpoint], A[(secondpoint + 1) % n]), secondpoint = (secondpoint + 1) % n;
			
		ans = max(ans, pov);
	}
	
	cout << ans << '\n';
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
	int tt = 1;

	while(tt--)
		task();

	return 0;
}

• Subtask 1: 0 / 12
• Subtask 2: 0 / 39
• Subtask 3: 0 / 49