제출 #1308351

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1308351		bornag	SIR (COI15_sir)	C++20	100 / 100	113 ms	14916 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;
pii A[MAXN];

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

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

vpii hullsort(vpii cords) {
	vpii 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() - 2], 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() - 2], upper.back(), x) == 1)
			upper.ppb();
		upper.pb(x);
	}
	
	upper.ppb();
	reverse(all(upper));
	if(!upper.empty()) 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;
	vpii cords(m);
	for(int i = 0; i < m; i++)
		cin >> cords[i].X >> cords[i].Y;
		
	sort(all(cords));
	vpii 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]);
		//sad pomicemo second point dok mozemo
		
		while(ccw(chull[holepoint], A[i], chull[(holepoint + 1) % m]) == 1)
			holepoint = (holepoint + 1) % m;
			
		if(i == 0) {
			while(ccw(chull[holepoint], A[i], chull[(holepoint - 1 + m) % m]) == 1)
				holepoint = (holepoint - 1 + m) % 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;
			
		//cout << holepoint << ' ' << secondpoint << ' ' << pov << '\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: 12 / 12
• Subtask 2: 39 / 39
• Subtask 3: 49 / 49