Pagini recente » Cod sursa (job #2110738) | Cod sursa (job #1792077) | Cod sursa (job #325873) | Cod sursa (job #2956683) | Cod sursa (job #1293902)
#include <fstream>
#define xmax 60000
using namespace std;
ifstream x ("poligon.in");
ofstream y ("poligon.out");
struct coord
{
int i;
int j;
};
int n,m;
coord p[802];
coord point[60001];
bool intersectie(coord A1, coord B1, coord A2, coord B2)
{
int x1=A1.i,x2=B1.i,x3=A2.i,x4=B2.i;
int y1=A1.j,y2=B1.j,y3=A2.j,y4=B2.j;
int d=(x1-x2)*(y3-y4)-(x3-x4)*(y1-y2);
if(d==0)
return false;
int xi=((x1*y2-x2*y1)*(x3-x4)-(x3*y4-x4*y3)*(x1-x2))/d;
int yi=((x1*y2-x2*y1)*(y3-y4)-(x3*y4-x4*y3)*(y1-y2))/d;
if(xi<min(x1,x2) || xi>max(x1,x2))
return false;
if(xi<min(x3,x4) || xi>max(x3,x4))
return false;
if(yi<min(y1,y2) || yi>max(y1,y2))
return false;
if(yi<min(y3,y4) || yi>max(y3,y4))
return false;
/*
y<<xi<<' '<<yi;
y<<'\n';
*/
return true;
}
int main()
{
int i,j;
x>>n>>m;
//Citesc punctele poligonului
for(i=1;i<=n;i++)
x>>p[i].i>>p[i].j;
p[n+1]=p[1];
//Citesc punctele de pe plan
for(i=1;i<=m;i++)
x>>point[i].i>>point[i].j;
point[0].i=xmax;
int nr=0;
for(i=1;i<=m;i++)
{
int nri=0;
point[0].j=point[i].j;
for(j=1;j<=n;j++)
{
if((point[i].i==p[j].i && point[i].j==p[j].j) || (point[i].i==p[j+1].i && point[i].j==p[j+1].j))
{
nri=1;
break;
}
if(intersectie(point[i],point[0],p[j],p[j+1])==true)
nri++;
}
if(nri%2==1)
nr++;
}
y<<nr<<'\n';
return 0;
}