Pagini recente » Cod sursa (job #270988) | Cod sursa (job #2468537) | Cod sursa (job #1570542) | Cod sursa (job #1270846) | Cod sursa (job #858265)
Cod sursa(job #858265)
#include <cstdio>
using namespace std;
struct punct{int x;int y;};
punct a[801],c;
int n,m,i,cnt;
int coliniaritate(punct c,punct a,punct b)
{
if((a.x-c.x)*(a.y-b.y)!=(a.x-b.x)*(a.y-c.y))return 0;
else
if((a.x-c.x)*(b.x-c.x)<=0&&(a.y-c.y)*(b.y-c.y)<=0) return 1;
return 0;
}
int sol(punct c, punct a, punct b)
{
if(a.x>b.x) return((a.x-b.x)*a.y-(a.y-b.y)*(a.x-c.x)>=c.y*(a.x-b.x));
else
if(a.x<b.x) return ((a.x-b.x)*a.y-(a.y-b.y)*(a.x-c.x)<=c.y*(a.x-b.x));
else
if(a.x==b.x) return((a.x-c.x)*(b.x-c.x)<=0&&(a.y-c.y)*(b.y-c.y)<=0);
}
int verif(punct c)
{
int i,cnt=0;
for(i=1;i<=n-1;i++) if(coliniaritate(c,a[i],a[i+1])) return 1;
if(coliniaritate(c,a[n],a[1])) return 1;
for(i=1;i<=n-1;i++) if((c.x-a[i].x)*(c.x-a[i+1].x)<=0&&sol(c,a[i],a[i+1]))cnt++;
if((c.x-a[n].x)*(c.x-a[1].x)<=0&&sol(c,a[n],a[1]))cnt++;
if(cnt%2==1)return 1;
return 0;
}
int main()
{
FILE *f=fopen("poligon.in","r");
FILE *g=fopen("poligon.out","w");
fscanf(f,"%d %d",&n,&m);
for(i=1;i<=n;i++)fscanf(f,"%d %d",&a[i].x,&a[i].y);
for(i=1;i<=m;i++)
{
fscanf(f,"%d %d",&c.x,&c.y);
if(verif(c)) cnt++;
}
fprintf(g,"%d",cnt);
fclose(f);
fclose(g);
}