Pagini recente » Cod sursa (job #2975753) | Cod sursa (job #254629) | Cod sursa (job #1517519) | Cod sursa (job #1380186) | Cod sursa (job #2500149)
#include <cstdio>
#include <algorithm>
using namespace std;
struct Point
{
long double x,y;
};
Point polig[805];
bool intersect(Point P1, Point P2, Point P3, Point P4)
{
long double a1=P1.y-P2.y;
long double b1=P2.x-P1.x;
long double c1=P1.x*P2.y-P2.x*P1.y;
long double a2=P3.y-P4.y;
long double b2=P4.x-P3.x;
long 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;
long double y=(c1*a2-a1*c2)/(-b1*a2+a1*b2);
long 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("%Lf%Lf", &polig[i].x, &polig[i].y);
for(j=1; j<=m; j++){
Point P;
scanf("%Lf%Lf", &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;
}