Submission #880128

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
880128	2023-11-28T19:42:19 Z	epicci23	SIR (COI15_sir)	C++17	100 / 100	121 ms	37364 KB

sir

#include "bits/stdc++.h"
using namespace std;
#define pb push_back
#define endl "\n" 
#define int long long
#define sz(x) ((int)(x).size())
#define all(x) (x).begin(),(x).end()

/* stuff you should look for
 * int overflow, array bounds
 * special cases (n=1?)
 * do smth instead of nothing and stay organized
 * WRITE STUFF DOWN
 * DON'T GET STUCK ON ONE APPROACH
 * SIMPLIFY THE PROBLEM
 * READ THE STATEMENT CAREFULLY
  !!! if there is an specified/interesting smth(i.e. constraint) in the statement,
  then you must be careful about that   
*/

struct P{
  	int 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);
	}
	int operator *(P other) {
		return x * other.y - y * other.x;
	}
	int comp(P A, P B) {
		return (A - *this) * (B - *this);
	}
};

vector<P> pgon,pepper,hull,cur_hull;

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;
}

void solve(){
  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(all(pepper));

  for(int xd=0;xd<2;xd++){
    for(P u : pepper){
      while(sz(cur_hull)>=2){
      	P a = cur_hull.end()[-2];
      	P b = cur_hull.end()[-1];
      	if(a.comp(b,u)>=0) break;
      	cur_hull.pop_back();
      }
      cur_hull.pb(u);
    }
    cur_hull.pop_back();
    for(P u:cur_hull) hull.pb(u);
    cur_hull.clear();
    reverse(all(pepper));
  }

   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;
	int area=0,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";
}

int32_t main(){

  cin.tie(0); ios::sync_with_stdio(0);
  
  int t=1;//cin >> t;
  while(t--) solve();

  return 0;
}

Subtask #1

12.0 / 12.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 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	0 ms	348 KB	Output is correct

Subtask #2

39.0 / 39.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	604 KB	Output is correct
2	Correct	1 ms	604 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	668 KB	Output is correct
6	Correct	1 ms	892 KB	Output is correct

Subtask #3

49.0 / 49.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	121 ms	20528 KB	Output is correct
2	Correct	117 ms	18644 KB	Output is correct
3	Correct	99 ms	21556 KB	Output is correct
4	Correct	29 ms	5712 KB	Output is correct
5	Correct	93 ms	16772 KB	Output is correct
6	Correct	108 ms	37364 KB	Output is correct