Cod sursa(job #597863)

Utilizator drywaterLazar Vlad drywater Data 23 iunie 2011 16:09:01
Problema Poligon Scor 0
Compilator cpp Status done
Runda Lista lui wefgef Marime 1.52 kb
#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;
}