oj.uz

Submission #244360

# Submission time Handle Problem Language Result Execution time Memory
244360 2020-07-03T18:15:52 Z MatesV13 Relay (COI16_relay) C++11
0 / 100
 5 ms 384 KB 
#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.0

# Verdict Execution time Memory Grader output
1 Incorrect 5 ms 384 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 19.0

# Verdict Execution time Memory Grader output
1 Incorrect 5 ms 384 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 5 ms 384 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 43.0

# Verdict Execution time Memory Grader output
1 Incorrect 5 ms 384 KB Output isn't correct
2 Halted 0 ms 0 KB -