Submission #552709

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
552709	2022-04-23T16:43:49 Z	nvujica	SIR (COI15_sir)	C++14	12 / 100	28 ms	4268 KB

sir

#include <bits/stdc++.h>

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

using namespace std;

const int maxn = 1e5 + 10, inf = 2e9;

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

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

Subtask #1

12.0 / 12.0

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

Subtask #2

0 / 39.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	340 KB	Output is correct
2	Correct	1 ms	340 KB	Output is correct
3	Correct	3 ms	424 KB	Output is correct
4	Correct	1 ms	340 KB	Output is correct
5	Correct	2 ms	408 KB	Output is correct
6	Incorrect	2 ms	468 KB	Output isn't correct
7	Halted	0 ms	0 KB	-

Subtask #3

0 / 49.0

#	Verdict	Execution time	Memory	Grader output
1	Runtime error	28 ms	4268 KB	Execution killed with signal 11
2	Halted	0 ms	0 KB	-