Pagini recente » Cod sursa (job #2653977) | Cod sursa (job #652821) | Cod sursa (job #1606807) | Cod sursa (job #1964144) | Cod sursa (job #597916)
Cod sursa(job #597916)
#include <fstream>
#include <algorithm>
using namespace std;
ifstream f("poligon.in");
ofstream o("poligon.out");
struct dreapta{int a; int b; int c;};
dreapta a[801];
struct banda{int v[801];};
banda bv[801];
int n,m,v[801][2],x,y,i,j,xu[801],nr,k,sol,sol2,s,xf[801],p,x1,y1,x2,y2;
int cmp(int aa,int b)
{
int x=xf[i+1]+xf[i];
x/=2;
return ((((-1)*x*a[aa].a-a[aa].c)*a[b].b)>(((-1)*x*a[b].a-a[b].c)*a[aa].b));
}
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];
}
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];
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+1] && maxi(v[j+1][0],v[j][0]>=xf[i]))
bv[i].v[++bv[i].v[0]]=j;
}
sort(bv[i].v+1,bv[i].v+bv[i].v[0]+1,cmp);
}
for (i=1;i<=m;i++)
{
f>>x>>y;
if (x<xf[1] || x>xf[p]) continue;
k=1;
while (k<=p) k*=2;
k/=2;
sol=0;
while (k>0)
{
if (sol+k<p && xf[sol+k]<=x) sol+=k;
k/=2;
}
sol2=0;
k=1;
while (k<=bv[sol].v[0]) k*=2;
k/=2;
while (k>0)
{
s=bv[sol].v[sol2+k];
if (v[s][0]>v[s+1][0])
{
x1=v[s+1][0];
y1=v[s+1][1];
x2=v[s][0];
y2=v[s][1];
}
else
{
x1=v[s][0];
y1=v[s][1];
x2=v[s+1][0];
y2=v[s+1][1];
}
if (x1==x2 && sol2+k<=bv[sol].v[0]) {sol2+=k; k/=2; continue;}
if (sol2+k<=bv[sol].v[0] && x1*y2+x2*y+x*y1-x1*y-x2*y1-x*y2>=0) sol2+=k;
k/=2;
}
if (sol2%2!=0) nr++;
}
o<<nr;
return 0;
}