Submission #552723

#	Time	Username	Problem	Language	Result	Execution time	Memory
552723		nvujica	SIR (COI15_sir)	C++14	12 / 100	188 ms	8828 KiB

sir

#include <bits/stdc++.h>

#define ll long long
#define fi first
#define se second

using namespace std;

const int maxn = 3e5 + 10;

int n, m, mini = 0;
int x[maxn];
int y[maxn];
int xs[maxn];
int ys[maxn];
vector <int> v;
vector <int> hull;

ll ccw(int xa, int ya, int xb, int yb, int xc, int yc){
	return (ll)xa * (yb - yc) + (ll)xb * (yc - ya) + (ll)xc * (ya - yb);
}

bool cmp(int a, int b){
	return ccw(xs[mini], ys[mini], xs[a], ys[a], xs[b], ys[b]) > 0;
}

int main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	
	cin >> n;
	
	for(int i = 0; i < n; i++){
		cin >> x[i] >> y[i];
	}
	
	if(ccw(x[0], y[0], x[1], y[1], x[2], y[2]) < 0){
		reverse(x, x + n);
		reverse(y, y + n);
	}
	
	cin >> m;
	
	for(int i = 0; i < m; i++){
		cin >> xs[i] >> ys[i];
		
		if(ys[i] < ys[mini] || ys[i] == ys[mini] && xs[i] < xs[mini]) mini = i;
	}
	
	//cout << mini << endl;
	
	for(int i = 0; i < m; i++){
		if(i != mini) v.push_back(i);
	}
		
	sort(v.begin(), v.end(), cmp);
	
//	for(int i = 0; i < v.size(); i++){
//		cout << v[i] << ' ';
//	}
//	cout << endl;

	if(m == 1) v.push_back(mini);

	hull.push_back(mini);
	hull.push_back(v[0]);
	
	for(int i = 1; i < m - 1; i++){
		while(hull.size() >= 2 && ccw(xs[hull[hull.size() - 2]], ys[hull[hull.size() - 2]], xs[hull.back()], ys[hull.back()], xs[v[i]], ys[v[i]]) <= 0){
			hull.pop_back();
		}
		
		hull.push_back(v[i]);
	}
	
	int h = hull.size();
	
//		for(int i = 0; i < hull.size(); i++){
//			cout << hull[i] << ' ';
//		}
//		cout << endl;
	
	int mini2 = 0;
	
	for(int i = 0; i < n; i++){
		if(y[i] < y[mini2] || y[i] == y[mini2] && x[i] < x[mini2]) mini2 = i;
	}
	
//	cout << mini2 << endl;
	
	int p = 0, q = (mini2 + 1) % n;
	ll povr = 0, maks = 0;
	
	for(int i = mini2; i < n + mini2; i++){
		while(ccw(x[i % n], y[i % n], xs[hull[p]], ys[hull[p]], xs[hull[(p + 1) % h]], ys[hull[(p + 1) % h]]) < 0){
			p++;
			p %= h;
		}
		
		while(ccw(x[i % n], y[i % n], xs[hull[p]], ys[hull[p]], x[(q + 1) % n], y[(q + 1) % n]) < 0){
			povr += ccw(x[i % n], y[i % n], x[q], y[q], x[(q + 1) % n], y[(q + 1) % n]);
			q++;
			q %= n;
		}
		
//		cout << i % n << ' ' << q << ' ' << p << endl;
		
		maks = max(maks, povr);
		
		povr -= ccw(x[i % n], y[i % n], x[(i + 1) % n], y[(i + 1) % n], x[q], y[q]);
	}
	
	cout << maks;
	
	return 0;
}

Compilation message (stderr)

sir.cpp: In function 'int main()':
sir.cpp:47:44: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   47 |   if(ys[i] < ys[mini] || ys[i] == ys[mini] && xs[i] < xs[mini]) mini = i;
      |                          ~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~
sir.cpp:86:42: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   86 |   if(y[i] < y[mini2] || y[i] == y[mini2] && x[i] < x[mini2]) mini2 = i;
      |                         ~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~

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