Submission #847915

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
847915	2023-09-10T20:04:30 Z	serifefedartar	SIR (COI15_sir)	C++17	100 / 100	122 ms	38644 KB

sir

#include <bits/stdc++.h>
using namespace std;
 
#define fast ios::sync_with_stdio(0);cin.tie(0);
#define s second
#define f first
typedef long long ll;
const ll MOD = 1e9 + 7;
const ll LOGN = 20;
const ll MAXN = 2e5 + 5;

struct P {
	ll x, y;
	
	void read() {
		cin >> x >> y;
	}
	P operator -(P other) {
		return P{x - other.x, y - other.y};		
	}
	bool operator <(P other) {
		return make_pair(x, y) < make_pair(other.x, other.y);
	}
	ll operator *(P other) {
		return x * other.y - y * other.x;
	}
	ll comp(P A, P B) {
		return (A - *this) * (B - *this);
	}
};

vector<P> pgon, pepper, hull, hull_now;
bool check(int l, int r, int in_hull) {
	ll cmp = pgon[l].comp(pgon[r], hull[in_hull]);
	if (cmp <= 0)
		return false;
	return true;
}

int main() {
	fast
	int N, M;
	cin >> N;

	pgon = vector<P>(N);
	for (int i = 0; i < N; i++)
		pgon[i].read();

	cin >> M;
	pepper = vector<P>(M);
	for (int i = 0; i < M; i++)
		pepper[i].read();
	sort(pepper.begin(), pepper.end());

	for (int rep = 0; rep < 2; rep++) {
		for (auto u : pepper) {
			while (hull_now.size() >= 2) {
				P A = hull_now.end()[-2];
				P B = hull_now.end()[-1];
				if (A.comp(B, u) >= 0)
					break;
				hull_now.pop_back();
			}
			hull_now.push_back(u);
		}

		hull_now.pop_back();
		for (auto u : hull_now)
			hull.push_back(u);
		hull_now.clear();
		reverse(pepper.begin(), pepper.end());
	}

	if (hull.size() == 0)
		hull.push_back(pepper[0]);

	int n = hull.size();
	int mx_hull = 0, mx_pgon = 0;
	for (int i = 0; i < n; i++) {
		if (hull[i].y > hull[mx_hull].y)
			mx_hull = i;
	}
	for (int i = 0; i < N; i++) {
		if (pgon[i].y > pgon[mx_pgon].y)
			mx_pgon = i;
	}
		
	int hull_ind = mx_hull;
	int r = (mx_pgon+1)%N;
	ll area = 0;
	ll ans = 0;
	for (int l = mx_pgon; l < 3*N; l++) {
		l %= N;
		while (pgon[l].comp(hull[hull_ind], hull[(hull_ind + 1) % n]) < 0)
			hull_ind = (hull_ind + 1) % n;

		while (check(l, (r+1)%N, hull_ind)) {
			area += pgon[l].comp(pgon[r], pgon[(r+1)%N]);
			r = (r + 1) % N;
		}

		ans = max(ans, area);
		area -= pgon[l].comp(pgon[(l+1)%N], pgon[r]);
		if (l == (mx_pgon == 0 ? N-1 : mx_pgon-1))
			break;
	}
	cout << ans << "\n";
}

Subtask #1

12.0 / 12.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	348 KB	Output is correct
2	Correct	0 ms	348 KB	Output is correct
3	Correct	0 ms	348 KB	Output is correct
4	Correct	1 ms	348 KB	Output is correct

Subtask #2

39.0 / 39.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	500 KB	Output is correct
2	Correct	1 ms	348 KB	Output is correct
3	Correct	1 ms	604 KB	Output is correct
4	Correct	1 ms	348 KB	Output is correct
5	Correct	1 ms	604 KB	Output is correct
6	Correct	2 ms	856 KB	Output is correct

Subtask #3

49.0 / 49.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	122 ms	10836 KB	Output is correct
2	Correct	120 ms	18612 KB	Output is correct
3	Correct	115 ms	21836 KB	Output is correct
4	Correct	29 ms	5724 KB	Output is correct
5	Correct	100 ms	16912 KB	Output is correct
6	Correct	105 ms	38644 KB	Output is correct