Pagini recente » Cod sursa (job #1577451) | Cod sursa (job #583138) | Cod sursa (job #824870) | Cod sursa (job #2573919) | Cod sursa (job #597863)
Cod sursa(job #597863)
#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;
int cmp(int aa,int b)
{
int x=xu[i+1]+xu[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));
}
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];
}
sort(xu+1,xu+n+1);
for (i=1;i<n;i++)
{
for (j=1;j<n;j++)
{
if (v[j][0]<=xu[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<xu[1] || x>xu[n]) continue;
k=1;
while (k<=n) k*=2;
k/=2;
sol=0;
while (k>0)
{
if (sol+k<=n && xu[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 (sol2+k<=bv[sol].v[0] && a[s].a*x+a[s].b*y+a[s].c<=0) sol2+=k;
k/=2;
}
nr+=sol2;
}
o<<nr;
return 0;
}