Pagini recente » Cod sursa (job #888568) | Cod sursa (job #3003376) | Cod sursa (job #1701693) | Cod sursa (job #3136314) | Cod sursa (job #220872)
Cod sursa(job #220872)
#include <fstream>
#define inf 0x3f3f3f
#define INFINIT -61000
using namespace std;
int n,m,nrsol;
struct punct
{
int x,y;
} poli[801],infr[60001];
struct punct2{ int x1,x2,y1,y2;};
struct benzi
{
int nr;
int X;
punct2 sir[1000];
}band[801];
int nr_benzi;
ofstream fout ("poligon.out");
ifstream f("poligon.in");
void citire()
{
f>>n>>m;
for(int i=0;i<n;++i)
{
f>>poli[i].x>>poli[i].y;
band[i].X=poli[i].x;
}
for(int i=0;i<m;++i)
f>>infr[i].x>>infr[i].y;
}
bool operator<(benzi a, benzi b)
{
return a.X<b.X;
}
void creeare()
{
nr_benzi=n;
for (int i=0;i<n-1;i++)
if (band[i].X==band[i+1].X)
{
nr_benzi--;
band[i].X=inf;
}
sort(band,band+n);
}
void baga_in_benzi()
{
for (int i=0;i<nr_benzi-1;i++)
for (int j=0;j<n;j++)
{
if(poli[j].x>band[i+1].X || poli[j+1].x<band[i].X)
continue;
band[i].sir[band[i].nr].x1=poli[j].x;
band[i].sir[band[i].nr].y1=poli[j].y;
band[i].sir[band[i].nr].x2=poli[j+1].x;
band[i].sir[band[i].nr++].y2=poli[j+1].y;
}
}
int cautbinar(punct p)
{
int st=0,dr=nr_benzi-1,mij;
while(st<dr)
{
mij=(st+dr)/2;
if(band[mij].X < p.x && band[mij+1].X> p.x)
return mij;
if(band[mij].X < p.x)
st=mij+1;
else
dr=mij;
}
return 0;
}
void anonim()
{
for(int i=0;i<m;i++)
{
int poz=cautbinar(infr[i]),numara;
punct aux;
aux.y=INFINIT;
aux.x=infr[i].x;
numara=0;
for (int j=0;j<band[poz].nr;j++)
{
long long det1=band[poz].sir[j].x1*band[poz].sir[j].y2 +
band[poz].sir[j].y2*aux.x +
band[poz].sir[j].x2*aux.y -
aux.x*band[poz].sir[j].y2 -
aux.y*band[poz].sir[j].x1 -
band[poz].sir[j].x2*band[poz].sir[j].y1;
long long det2=band[poz].sir[j].x1*band[poz].sir[j].y2 +
band[poz].sir[j].y2*infr[i].x +
band[poz].sir[j].x2*infr[i].y -
infr[i].x*band[poz].sir[j].y2 -
infr[i].y*band[poz].sir[j].x1 -
band[poz].sir[j].x2*band[poz].sir[j].y1;
if(det1*det2<0)
numara++;
}
if(numara%2)
nrsol++;
}
}
int main()
{
citire();
sort(band,band+n);
creeare();
baga_in_benzi();
anonim();
fout<<nrsol<<endl;
return 0;
}