Pagini recente » Cod sursa (job #3252514) | Cod sursa (job #2246680) | Cod sursa (job #2713627) | Cod sursa (job #2108172) | Cod sursa (job #2629329)
#include <bits/stdc++.h>
using namespace std;
ifstream f("poligon.in"); ofstream g("poligon.out");
typedef long long ll;
const int N=805;
vector<int> v[N];
bool vertical;
int n,k,t[N];
double mid;
struct pct {int x,y;} p[N];
double eval(pct a, pct b, double m)
{ return a.y+(b.y-a.y)*(m-a.x)/((double)b.x-a.x);}
bool comp(int x, int y)
{ return eval(p[x],p[x+1],mid)<eval(p[y],p[y+1],mid);}
ll det(pct a, pct b, pct c)
{ return 1LL*a.x*b.y+1LL*b.x*c.y+1LL*c.x*a.y
-1LL*a.x*c.y-1LL*b.x*a.y-1LL*c.x*b.y;
}
bool compare(pct a, pct b)
{ if(a.x == b.x) return a.y<b.y;
return a.x<b.x;
}
bool ok(int i, pct a)
{ ll D;
if(compare(p[i],p[i+1])) D=det(p[i],p[i+1],a);
else D=det(p[i+1],p[i],a);
if(!D) {vertical=1; return 1;}
return D>0;
}
void precompute()
{ sort(t+1,t+n+1);
t[0]=-1; p[n+1]=p[1];
for(int i=1;i<=n;i++)
if(t[i]!=t[k]) t[++k]=t[i];
t[k+1]=t[k]+100;
for(int i=1;i<=k;i++)
{ for(int j=1;j<=n;j++)
if((p[j].x<=t[i]&&t[i+1]<=p[j+1].x)||
(p[j+1].x<=t[i]&&t[i+1]<=p[j].x)) v[i].push_back(j);
mid=(double)(t[i]+t[i+1])/2;
sort(v[i].begin(),v[i].end(),comp);
}
}
int main()
{ int m;
f>>n>>m;
for(int i=1;i<=n;i++) {f>>p[i].x>> p[i].y; t[i]=p[i].x;}
precompute();
int ans=0;
for(int i=1;i<=m;i++)
{ pct c;
f>>c.x>>c.y;
int poz=0,cnt=-1;
for(int i=1<<9;i;i>>=1)
if(poz+i<=k && t[poz+i]<c.x) poz+=i;
vertical=0;
for(int i=1<<9;i;i>>=1)
if(cnt+i<v[poz].size() && ok(v[poz][i+cnt],c)) cnt+=i;
cnt++;
ans+=((cnt&1)||(vertical));
}
g<<ans; g.close(); f.close(); return 0;
}