Pagini recente » Cod sursa (job #2939703) | Cod sursa (job #2598248) | Cod sursa (job #125458) | Cod sursa (job #3232615) | Cod sursa (job #998298)
Cod sursa(job #998298)
#include <stdio.h>
#define NMAX 805
#define MMAX 60005
struct Punct{double x,y;};
Punct P[NMAX];
Punct PCT[MMAX];
int n,m;
void read()
{
scanf("%d %d\n",&n,&m);
int i,a,b;
for (i=1;i<=m;i++)
{
scanf("%d %d\n",&a,&b);
P[i].x=a;
P[i].y=b;
}
for (i=1;i<=n;i++)
{
scanf("%d %d\n",&a,&b);
PCT[i].x=a;
PCT[i].y=b;
}
}
int inside(Punct M)
{
int i,intersect=0;
double t,cy;
P[m+1]=P[1];
for (i=1;i<=m;i++)
{
if ((P[i].x<M.x && M.x<P[i+1].x)||(P[i].x>M.x && M.x>P[i+1].x))
{
t=(M.x-P[i+1].x)/(P[i].x-P[i+1].x);
cy=t*P[i].y+(1-t)*P[i+1].y;
if (M.y==cy) return 0;
else
if (M.y>cy) intersect++;
}
if (P[i].x==M.x && P[i].y>=M.y && P[i+1].y<=M.y)
return 1;
if (P[i].x==M.x && P[i].y<=M.y)
{
if (P[i].y==M.y) return 0;
if (P[i+1].x==M.x)
{
if ((P[i].y<=M.y && M.y<=P[i+1].y) || (P[i].y>=M.y && M.y>=P[i+1].y))
return 0;
}
else
if (P[i+1].x>M.x) intersect++;
}
}
if (intersect%2) return 1;
return 0;
}
void solve()
{
int nr=0,i;
for (i=1;i<=n;i++)
if (inside(PCT[i]))
nr++;
printf("%d\n",nr);
}
int main()
{
freopen ("poligon.in","r",stdin);
freopen ("poligon.out","w",stdout);
read();
solve();
fclose(stdin);
fclose(stdout);
return 0;
}