Submission #245490

#	Time	Username	Problem	Language	Result	Execution time	Memory
245490		MatesV13	SIR (COI15_sir)	C++11	51 / 100	142 ms	896 KiB

sir

#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 / 12
• Subtask 2: 39 / 39
• Subtask 3: 0 / 49