Pagini recente » Cod sursa (job #2393104) | Cod sursa (job #1184075) | Cod sursa (job #3123687) | Cod sursa (job #2038982) | Cod sursa (job #967143)
Cod sursa(job #967143)
#include<stdio.h>
#include<algorithm>
#define maxn 805
#define maxm 60005
using namespace std;
struct point{double x,y;};
point v[maxn],p[maxm];
int n,m,sol;
int inter;
void cit()
{
int i;
scanf("%d%d",&n,&m);
for(i=1;i<=n;i++) scanf("%lf%lf",&v[i].x,&v[i].y);
for(i=1;i<=m;i++) scanf("%lf%lf",&p[i].x,&p[i].y);
v[0]=v[n]; v[n+1]=v[1];
}
int between_o(point a,point b,point c)
{
if(b.x<a.x && c.x>a.x) return 1;
if(b.x>a.x && c.x<a.x) return 1;
return 0;
}
int between_v(point a,point b,point c)
{
if(b.x==a.x && c.x==a.x)
{
if(b.y>a.y && c.y<a.y) return 1;
if(b.y<a.y && c.y>a.y) return 1;
}
return 0;
}
double intersect(point a,point b,double xx)
{
return (xx-a.x)*(b.y-a.y)/(b.x-a.x)+a.y;
}
double side(point a,point b,point c)
{
return (c.x-a.x)*(b.y-a.y)-(c.y-a.y)*(b.x-a.x);
}
int search(int k)
{
int i;
double yc;
point aux=p[k];
aux.y=aux.y+1;
inter=0;
for(i=1;i<=n;i++)
{
if(between_o(p[k],v[i],v[i+1]))
{
yc=intersect(v[i],v[i+1],p[k].x);
if(yc==p[k].y) return 1;
else
if(yc<p[k].y) inter++;
}
if(v[i].x==p[k].x && v[i].y==p[k].y) return 1;
if(between_v(p[k],v[i],v[i+1])) return 1;
if(v[i].x==p[k].x && v[i].y<p[k].y && side(p[k],aux,v[i-1])*side(p[k],aux,v[i+1])<0) inter++;
}
if(inter%2==1) return 1;
return 0;
}
void solve()
{
int i;
for(i=1;i<=m;i++) sol+=search(i);
}
int main()
{
freopen("poligon.in","r",stdin);
freopen("poligon.out","w",stdout);
cit();
solve();
printf("%d",sol);
fclose(stdin);
fclose(stdout);
return 0;
}