Pagini recente » Cod sursa (job #16624) | Cod sursa (job #855427) | Cod sursa (job #222406) | Cod sursa (job #1082844) | Cod sursa (job #597951)
Cod sursa(job #597951)
#include <fstream>
#include <algorithm>
#define fi first
#define se second
#define LL long long
using namespace std;
ifstream f("poligon.in");
ofstream o("poligon.out");
struct dreapta{int a; int b; int c;};
dreapta a[801];
struct banda{pair<double,int> v[801];};
banda bv[801];
int k,n,m,v[801][2],x,y,i,j,xu[801],nr,l,ret,mij,h,sol,sol2,s,xf[801],p,pe_lat;
LL u;
inline int mini(int a,int b)
{
if (a<b) return a;
return b;
}
inline int maxi(int a,int b)
{
if (a<b) return b;
return a;
}
int main(void)
{
f>>n>>m;
for (i=1;i<=n;i++)
{
f>>v[i][0]>>v[i][1];
if (i>1)
{
a[i-1].a=v[i-1][1]-v[i][1];
a[i-1].b=v[i][0]-v[i-1][0];
a[i-1].c=v[i-1][0]*v[i][1]-v[i-1][1]*v[i][0];
if (a[i-1].b<0) {a[i-1].a*=(-1); a[i-1].b*=(-1); a[i-1].c*=(-1);}
}
xu[i]=v[i][0];
}
v[i][0]=v[1][0];
v[i][1]=v[1][1];
a[i-1].a=v[i-1][1]-v[i][1];
a[i-1].b=v[i][0]-v[i-1][0];
a[i-1].c=v[i-1][0]*v[i][1]-v[i-1][1]*v[i][0];
if (a[i-1].b<0)
{a[i-1].a*=(-1); a[i-1].b*=(-1); a[i-1].c*=(-1);}
sort(xu+1,xu+n+1);
p=0;
for (i=1;i<=n;i++)
{
if (i==1 || xu[i]!=xu[i-1])
xf[++p]=xu[i];
}
for (i=1;i<p;i++)
{
for (j=1;j<=n;j++)
{
if (mini(v[j][0],v[j+1][0])<=xf[i] && maxi(v[j+1][0],v[j][0])>=xf[i+1])
{
double aa,b,c,xx,yy;
aa=a[j].a;
b=a[j].b;
c=a[j].c;
xx=xf[i]+xf[i+1];
xx/=2;
yy=(-1)*(aa*x+c)/b;
bv[i].v[++bv[i].v[0].se]=make_pair(yy,j);
}
}
sort(bv[i].v+1,bv[i].v+bv[i].v[0].se+1);
}
for (i=1;i<=m;i++)
{
f>>x>>y;
if (x<xf[1] || x>xf[p]) continue;
l=1;
h=p;
ret=-1;
while (l<=h)
{
mij=l+(h-l)/2;
if (xf[mij]<=x && x<=xf[mij+1])
{
ret=mij;
l=mij+1;
}
else
{
if (x<=xf[mij])
h=mij-1;
else l=mij+1;
}
}
sol=ret;
l=1;
h=bv[sol].v[0].se;
ret=-1;
while (l<=h)
{
mij=l+(h-l)/2;
s=bv[sol].v[mij].se;
u=a[s].a*x+a[s].b*y+a[s].c;
if (u==0) pe_lat=1;
if (u>0) {ret=mij; l=mij+1;}
else h=mij-1;
}
sol2=ret;
if (sol2%2!=0 || pe_lat) nr++;
pe_lat=0;
}
o<<nr<<"\n";
return 0;
}