#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int mxN=1e5;
int n, m, ans;
ll xa[mxN], ya[mxN], xb[2*mxN], yb[2*mxN];
struct ts {
int li, ri;
ll lx, ly, rx, ry;
};
ll cp(ll x1, ll y1, ll x2, ll y2, ll x3, ll y3) {
return (y3-y1)*(x2-x1)-(y2-y1)*(x3-x1);
}
ts gts(ll x, ll y) {
ts r;
if(cp(x, y, xb[m-1], yb[m-1], xb[0], yb[0])<0) {
int lb=0, rb=m-2;
while(lb<rb) {
int mb=(lb+rb+1)/2;
if(cp(x, y, xb[m-1], yb[m-1], xb[mb], yb[mb])<0&&cp(x, y, xb[mb-1], yb[mb-1], xb[mb], yb[mb])<0)
lb=mb;
else
rb=mb-1;
}
r.li=lb;
lb=1, rb=m-1;
while(lb<rb) {
int mb=(lb+rb+1)/2;
if(cp(x, y, xb[mb], yb[mb], xb[0], yb[0])<0&&cp(x, y, xb[mb], yb[mb], xb[mb-1], yb[mb-1])<0)
lb=mb;
else
rb=mb-1;
}
r.ri=lb;
} else {
int lb=0, rb=m-2;
while(lb<rb) {
int mb=(lb+rb+1)/2;
if(cp(x, y, xb[m-1], yb[m-1], xb[mb], yb[mb])>=0&&cp(x, y, xb[mb-1], yb[mb-1], xb[mb], yb[mb])>=0)
lb=mb;
else
rb=mb-1;
}
r.li=lb;
lb=1, rb=m-1;
while(lb<rb) {
int mb=(lb+rb+1)/2;
if(cp(x, y, xb[mb], yb[mb], xb[0], yb[0])>=0&&cp(x, y, xb[mb], yb[mb], xb[mb-1], yb[mb-1])>=0)
lb=mb;
else
rb=mb-1;
}
r.ri=lb;
}
if(r.li<r.ri)
r.li+=m;
r.lx=r.rx=x;
r.ly=r.ry=y;
return r;
}
bool wt(ll x, ll y, ts t) {
return t.li>t.ri&&cp(xb[t.li], yb[t.li], xb[t.ri], yb[t.ri], x, y)>0&&cp(t.lx, t.ly, xb[t.li], yb[t.li], x, y)<0&&cp(t.rx, t.ry, xb[t.ri], yb[t.ri], x, y)>0;
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cin >> n;
for(int i=0; i<n; ++i)
cin >> xa[i] >> ya[i];
cin >> m;
for(int i=0; i<m; ++i)
cin >> xb[i] >> yb[i];
memcpy(xb+m, xb, 8*m);
memcpy(yb+m, yb, 8*m);
ts re1=gts(xa[0], ya[0]), re2=re1;
for(int i=0; i<n; ++i) {
if(wt(xa[i], ya[i], re1))
continue;
ts tr=gts(xa[i], ya[i]);
if(tr.li^re2.li?tr.li<re2.li:cp(re2.lx, re2.ly, xb[tr.li], yb[tr.li], tr.lx, tr.ly)>0) {
re2.li=tr.li;
re2.lx=tr.lx;
re2.ly=tr.ly;
}
if(tr.ri^re2.ri?tr.ri>re2.ri:cp(re2.rx, re2.ry, xb[tr.ri], yb[tr.ri], tr.rx, tr.ry)<0) {
re2.ri=tr.ri;
re2.rx=tr.rx;
re2.ry=tr.ry;
}
}
for(int i=0; i<n; ++i)
ans+=!wt(xa[i], ya[i], re2);
cout << ans-1;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
504 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
504 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
504 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
504 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
