Pagini recente » Cod sursa (job #2331524) | Cod sursa (job #2432263) | Cod sursa (job #1415319) | Cod sursa (job #2414002) | Cod sursa (job #2242016)
#include <iostream>
#include <fstream>
#include <cassert>
#include <map>
using namespace std;
struct point
{
long double x,y;
}v[1005];
map< pair<int,int>,int > m;
long long det(point A,point B,point C)
{
return 1LL*A.x*B.y+B.x*A.y+C.x*A.y-A.y*B.x-B.y*C.x-C.y*A.x;
}
long long sgn(long long a)
{
if(a<0) return -1;
if(a==0) return 0;
return 1;
}
int n,q,x,y;
long double A,B;
int check(long double x,long double y)
{
point pct;
pct.x=x;pct.y=y;
if(m[make_pair(x,y)])
return 1;
int cate=0;
for(int i=1;i<=n;i++)
{
if(det(v[i],v[i+1],pct)==0&&min(v[i].x,v[i+1].x)<=x&&max(v[i].x,v[i+1].x)>=x&&min(v[i].y,v[i+1].y)<=y&&max(v[i].y,v[i+1].y)>=y)
return 1;
if(min(v[i].x,v[i+1].x)>x||(max(v[i].x,v[i+1].x)<x))
continue;
if(v[i].x==v[i+1].x)
{
/*if(x==v[i].x&&max(v[i].y,v[i+1].y)>=y)
cate++;*/
}
else
{
A=((long double)(v[i+1].y-v[i].y))/((long double)(v[i+1].x-v[i].x));
B=(long double)(v[i].y-A*v[i].x);
cate+=((long double)A*x+B>=(long double) y);
}
}
return (cate%2);
}
int main()
{
ifstream f("poligon.in");
ofstream g("poligon.out");
f>>n>>q;
for(int i=1;i<=n;i++)
{
f>>v[i].x>>v[i].y;
m[make_pair(v[i].x,v[i].y)]=1;
}
v[n+1]=v[1];
int ans=0;
for(int cnt=1;cnt<=q;cnt++)
{
f>>x>>y;
ans+=check(x,y);
}
g<<ans;
return 0;
}