oj.uz

Submission #602315

# Submission time Handle Problem Language Result Execution time Memory
602315 2022-07-22T21:33:56 Z nvujica SIR (COI15_sir) C++14
12 / 100
 182 ms 15992 KB 
#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];
	}

	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;
	}
	
	for(int i = 0; i < m; i++){
		if(i != mini) v.push_back(i);
	}
		
	sort(v.begin(), v.end(), cmp);

	hull.push_back(mini);
	
	for(int i = 0; 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();
	
	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;
	}
	
	int p = 0, q = (mini2 + 1) % n;
	ll povr = 0, maks = 0;
	
	for(int i = mini2; i < mini2 + n; 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:66:42: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   66 |   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 340 KB Output is correct
4 Correct 1 ms 332 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 2 ms 468 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 2 ms 468 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 Correct 180 ms 15992 KB Output is correct
2 Correct 182 ms 15696 KB Output is correct
3 Correct 166 ms 14036 KB Output is correct
4 Correct 36 ms 4556 KB Output is correct
5 Correct 152 ms 12676 KB Output is correct
6 Incorrect 125 ms 13080 KB Output isn't correct
7 Halted 0 ms 0 KB -