Submission #244360

#	Time	Username	Problem	Language	Result	Execution time	Memory
244360		MatesV13	Relay (COI16_relay)	C++11	0 / 100	5 ms	384 KiB

relay

#include <bits/stdc++.h>
using namespace std;
bool v[100005]; int n, m;
struct point{
	long long x;
	long long y;
} br[100005], vr[100005];
struct nagib{
	long long brojnik;
	long long nazivnik;
} minnag, maxnag, nag;
inline bool jeveci(nagib a, nagib b){
	return (a.brojnik * b.nazivnik) > (b.brojnik * a.nazivnik);
}
void donagib (int idx){
	minnag.nazivnik = br[idx].x-vr[0].x;
	minnag.brojnik = br[idx].y-vr[0].y;
	maxnag.nazivnik = br[idx].x-vr[0].x;
	maxnag.brojnik = br[idx].y-vr[0].y;
	for (int i=1; i<m; i++){
		nag.nazivnik = br[idx].x-vr[i].x;
		nag.brojnik = br[idx].y-vr[i].y;
		if (jeveci(nag, maxnag)) maxnag=nag;
		if (jeveci(minnag, nag)) minnag=nag;
	}
} queue<int> xxx;
void solve (int vrh){
	donagib(vrh);
	for (int i=0; i<n; i++){
		if (i==vrh) continue;
		nag.nazivnik = br[vrh].x-br[i].x;
		nag.brojnik = br[vrh].y-br[i].y;
		bool iz = jeveci(nag, maxnag) || jeveci(minnag, nag);
		if (iz){
			v[i]=1;
			if (vrh==0) xxx.push(i);
		} 
	}
	if (vrh==0){
		while (!xxx.empty()){
			int idx=xxx.front();
			solve(idx); xxx.pop();
		}
	}
}
int main (){
ios::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
cin >> n;
for (int i=0; i<n; i++)
	cin >> br[i].x >> br[i].y;
cin >> m;
for (int i=0; i<m; i++)
	cin >> vr[i].x >> vr[i].y;
solve(0); int ans=1;
for (int i=1; i<n; i++) if (v[i]) ans++;
cout << ans << endl;
return 0;
}

• Subtask 1: 0 / 18
• Subtask 2: 0 / 19
• Subtask 3: 0 / 20
• Subtask 4: 0 / 43