#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;
}
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
5 ms |
384 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
5 ms |
384 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
5 ms |
384 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
5 ms |
384 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
