Pagini recente » Cod sursa (job #2813096) | Cod sursa (job #2874866) | Cod sursa (job #458642) | Cod sursa (job #824133) | Cod sursa (job #2500053)
#include <cstdio>
#include <algorithm>
using namespace std;
struct Point
{
int x,y;
};
Point polig[60005];
bool intersect(Point P1, Point P2, Point P3, Point P4)
{
double a1=P1.y-P2.y;
double b1=P2.x-P1.x;
double c1=P1.x*P2.y-P2.x*P1.y;
double a2=P3.y-P4.y;
double b2=P4.x-P3.x;
double c2=P3.x*P4.y-P4.x*P3.y;
if(a1*P4.x+b1*P4.y+c1==0)
return 0;
if(a1-a2==0)
return 0;
if(-b1*a2+a1*b2==0)
return 0;
double y=(c1*a2-a1*c2)/(-b1*a2+a1*b2);
double x=((c2-c1)-y*(b1-b2))/(a1-a2);
if(min(P1.x, P2.x)<=x && x<=max(P1.x,P2.x) && min(P1.y, P2.y)<=y && y<=max(P1.y, P2.y)){
if(min(P3.x, P4.x)<=x && x<=max(P3.x,P4.x) && min(P3.y, P4.y)<=y && y<=max(P3.y, P4.y))
return 1;
else
return 0;
}
else
return 0;
}
int main()
{ freopen("poligon.in", "r", stdin);
freopen("poligon.out", "w", stdout);
int n,m,i,sol,ans=0,j;
scanf("%d%d", &n, &m);
for(i=1; i<=n; i++)
scanf("%d%d", &polig[i].x, &polig[i].y);
for(j=1; j<=m; j++){
Point P;
scanf("%d%d", &P.x, &P.y);
sol=0;
for(i=1; i<n; i++)
sol+=intersect(polig[i], polig[i+1], {-17, -19}, P);
sol+=intersect(polig[i], polig[1], {-17, -19}, P);
if(sol%2==1)
ans++;
}
printf("%d", ans);
return 0;
}