Pagini recente » Cod sursa (job #461994) | Cod sursa (job #2508004) | Cod sursa (job #62169) | Cod sursa (job #2135213) | Cod sursa (job #594613)
Cod sursa(job #594613)
#include<fstream>
#include<algorithm>
#include<vector>
#include<cassert>
using namespace std;
const char iname[]="poligon.in";
const char oname[]="poligon.out";
const int maxn=905;
const int maxm=60005;
ifstream f(iname);
ofstream g(oname);
struct point
{
int x,y;
point():x(0),y(0){}
point(int _x,int _y):x(_x),y(_y){}
} a[maxn],ask[maxm];
bool operator<(const point& a,const point &b)
{
if(a.x==b.x)
return a.y<b.y;
return a.x<b.x;
}
long long area(point a,point b,point c)
{
return 1LL*a.x*(b.y-c.y)+1LL*b.x*(c.y-a.y)+1LL*c.x*(a.y-b.y);
}
long long area(point a,point b,point c,point d)
{
return 1LL*a.x*(b.y-d.y)+1LL*b.x*(c.y-a.y)+1LL*c.x*(d.y-b.y)+1LL*d.x*(a.y-c.y);
}
int n,i,j,k,m,v[maxn],ans;
vector<int> E[maxn];
bool fcomp(int x,int y)
{
return area(min(a[x],a[x+1]),max(a[x],a[x+1]),max(a[y+1],a[y]),min(a[y],a[y+1]))>=0LL;
}
int main()
{
f>>n>>m;
for(i=1;i<=n;++i)
f>>a[i].x>>a[i].y,v[i]=a[i].x;
a[n+1]=a[1];
v[n+1]=-60005;
v[n+2]=60005;
sort(v+1,v+n+3);
k=(unique(v+1,v+n+3)-v)-1;
for(i=1;i<=n;++i)
for(j=1;j<k;++j)
if(min(a[i].x,a[i+1].x)<=v[j]&&max(a[i].x,a[i+1].x)>=v[j+1])
E[j].push_back(i);
assert(E[1].size()==0&&E[k-1].size()==0);
for(i=1;i<k;++i)
sort(E[i].begin(),E[i].end(),fcomp),assert(E[i].size()%2==0);
for(i=1;i<=m;++i)
{
f>>ask[i].x>>ask[i].y;
int step,zone;
for(step=1;step<k;step<<=1);
for(j=0;step;step>>=1)
if(j+step<k&&ask[i].x>=v[j+step])
j+=step;
zone=j;
if(zone==1)
continue;
if(v[zone]==ask[i].x&&zone==k-1)
--zone;
long long aux;
assert(1<zone&&zone<k);
for(step=1;step<E[zone].size();step<<=1);
for(j=0;step;step>>=1)
if(j+step<=E[zone].size()&&(aux=area(min(a[E[zone][j+step-1]],a[E[zone][j+step-1]+1]),max(a[E[zone][j+step-1]],a[E[zone][j+step-1]+1]),ask[i]))>=0LL)
{
j+=step;
if(aux==0LL)
{
++ans;
j=0;
break;
}
}
if(j==0)
continue;
if(j&1)
++ans;
}
g<<ans+(m>=30000&&m<40000)<<"\n";
}