Pagini recente » Cod sursa (job #169798) | Cod sursa (job #1114915) | Cod sursa (job #1410668) | Cod sursa (job #2299342) | Cod sursa (job #967142)
Cod sursa(job #967142)
#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.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)+a.y*(b.x-a.x))/(b.x-a.x);
}
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)
{
if(v[i].y==p[k].y) return 1;
if(v[i+1].x==p[k].x && between_v(v[i],v[i+1],p[k])) return 1;
if(v[i].y<p[k].y)
if( (v[i+1].x>p[k].x && v[i-1].x<p[k].x) || (v[i+1].x<p[k].x && v[i-1].x>p[k].x) )
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;
}