oj.uz

Submission #245490

# Submission time Handle Problem Language Result Execution time Memory
245490 2020-07-06T14:14:18 Z MatesV13 SIR (COI15_sir) C++11
51 / 100
 142 ms 896 KB 
#include <bits/stdc++.h>
using namespace std;
struct tocka{
	long long x;
	long long y;
} sir[3005], pap[3005];
long long n, m;
long long p(tocka a, tocka b, tocka c){
	long long povrsina=0;
	povrsina += a.x*(b.y-c.y);
	povrsina += b.x*(c.y-a.y);
	povrsina += c.x*(a.y-b.y);
	return povrsina;
}
bool check (int idx1, int idx2){
	if (idx2-idx1==n-1){
		if (m) return 0;
		return 1;
	}
	bool manje=0, vise=0;
	if (p(sir[(idx1)%n], sir[(idx2+1)%n], sir[(idx2)%n])<=0) manje=1; else vise=1;
	for (int i=0; i<m; i++){
		if (p(sir[(idx1)%n], pap[i], sir[(idx2)%n])<=0) manje=1;
		if (p(sir[(idx1)%n], pap[i], sir[(idx2)%n])>=0) vise=1;
		if (manje and vise) return 0;
	} return 1;
}
long long solve (long long lo, long long hi){
	long long prvi=lo;
	while (lo<hi){
		long long mid = (lo+hi+1)/2;
		if (check(prvi, mid)) lo=mid;
		else hi=mid-1;
	}
	long long drugi=lo;
	long long povrsina=0;
	for (int i=prvi+1; i<=drugi-1; i++){
		povrsina += abs(p(sir[(prvi)%n], sir[(i)%n], sir[(i+1)%n]));
//		cout << prvi << " " << i << " " << i+1 << " : " << abs(p(sir[(prvi)%n], sir[(i)%n], sir[(i+1)%n])) << endl;
	}
//	cout << prvi << " " << drugi << "   : " << povrsina << endl;
	return povrsina;
}
int main (){
ios::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
	cin >> n;
	for (int i=0; i<n; i++)
		cin >> sir[i].x >> sir[i].y;
	cin >> m;
	for (int i=0; i<m; i++)
		cin >> pap[i].x >> pap[i].y;
	long long ans=0;
	for (int i=0; i<n; i++)
		ans = max(ans, solve(i, i+n-1));
	cout << ans << endl;
return 0;
}

/*
4
-1000000000 -1000000000
-1000000000 1000000000
1000000000 1000000000
1000000000 -1000000000
0

4
-1000000000 -1000000000
1000000000 -1000000000
1000000000 1000000000
-1000000000 1000000000
0

3
1 1
0 0
1 0
0

3
1 1
0 0
0 1
0
*/

Subtask #1
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 384 KB Output is correct
2 Correct 6 ms 384 KB Output is correct
3 Correct 5 ms 384 KB Output is correct
4 Correct 5 ms 384 KB Output is correct

Subtask #2
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 384 KB Output is correct
2 Correct 19 ms 512 KB Output is correct
3 Correct 137 ms 512 KB Output is correct
4 Correct 27 ms 384 KB Output is correct
5 Correct 11 ms 384 KB Output is correct
6 Correct 142 ms 512 KB Output is correct

Subtask #3
0 / 49.0

# Verdict Execution time Memory Grader output
1 Runtime error 6 ms 896 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -