oj.uz

Submission #847912

# Submission time Handle Problem Language Result Execution time Memory
847912 2023-09-10T19:46:59 Z serifefedartar SIR (COI15_sir) C++17
0 / 100
 123 ms 20852 KB 
#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) {
	int 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
0 / 12.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 344 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 600 KB Output is correct
2 Correct 1 ms 600 KB Output is correct
3 Incorrect 2 ms 600 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 49.0

# Verdict Execution time Memory Grader output
1 Incorrect 123 ms 20852 KB Output isn't correct
2 Halted 0 ms 0 KB -