Pagini recente » Cod sursa (job #40366) | Cod sursa (job #1851512) | Cod sursa (job #1146940) | Cod sursa (job #340247) | Cod sursa (job #1293865)
#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 intersection(coord A1, coord B1, coord A2, coord B2)
{
int x1,x2,x3,x4;
int y1,y2,y3,y4;
x1=A1.i; x2=B1.i; x3=A2.i; x4=B2.i;
y1=A1.j; y2=B1.j; y3=A2.j; y4=B2.j;
int d;
d=(x1-x2)*(y3-y4)-(y1-y2)*(x3-x4);
if(d==0)
return false;
int xi,yi;
xi=((x3-x4)*(x1*y2-y1*x2)-(x1-x2)*(x3*y4-y3*x4))/d;
yi=((y3-y4)*(x1*y2-y1*x2)-(y1-y2)*(x3*y4-y3*x4))/d;
if(xi<min(x1,x2) || xi>max(x1,x2))
return false;
if(yi<min(y1,y2) || yi>max(y1,y2))
return false;
if(xi<min(x3,x4) || xi>max(x3,x4))
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;
int nr=0;
point[0].i=xmax;
for(j=1;j<=m;j++)
{
point[0].j=point[j].j;
int nri=0;
for(i=1;i<=n;i++)
{
if((point[j].i==p[i].i && point[j].j==p[i].j) || (point[j].i==p[i+1].i && point[j].j==p[i+1].j))
{
nri=1;
break;
}
if(intersection(point[j],point[0],p[i],p[i+1])==true)
{
nri++;
//y<<j<<" "<<i<<"\n";
}
}
if(nri%2==1)
nr++;
//y<<nri<<'\n';
}
y<<nr<<'\n';
return 0;
}