Cod sursa(job #732347)

Utilizator mihai995mihai995 mihai995 Data 10 aprilie 2012 12:05:16
Problema Poligon Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.82 kb
#include <fstream>
#include <algorithm>
#include <vector>
using namespace std;

const int N=805,M=60005;

int X[N],n,nr,rez;
vector<int> edge[M];

ifstream in("poligon.in");
ofstream out("poligon.out");

inline void sch(int& a,int& b)
{
    int c=a;a=b;b=c;
}

struct Point
{
    int x,y;
} poli[N];

struct Dr1
{
    double a,b;
    int x,y;
    void det(Point A,Point B)
    {
        a=(double)(B.y-A.y)/(B.x-A.x);
        b=(double)(B.x*A.y-A.x*B.y)/(B.x-A.x);
        if (A.x<B.x)
        {
            x=A.x;
            y=B.x;
        }
        else
        {
            x=B.x;
            y=A.x;
        }
    }
    bool inside(int X,int Y)
    {
        return x<=X && Y<=y;
    }
} line[N];

struct Dreapta
{
    double a,b,y;
    void copy(Dr1 X,int x)
    {
        a=X.a;
        b=X.b;
        y=a*x+b;
    }
    double height(int x)
    {
        return a*x+b;
    }
};
vector<Dreapta> inter[N];

inline bool cmp(const Dreapta& a,const Dreapta& b)
{
    return a.y<b.y;
}

void add(vector<Dreapta> &v,Dr1 X,int x)
{
    Dreapta a;
    a.copy(X,x);
    v.push_back(a);
}

int bs(int v[],int x)
{
    if (x<v[1] || v[v[0]]<x)
        return -1;
    int i,step=1<<9;
    for (i=0;step;step>>=1)
        if (i+step<=v[0] && v[i+step]<x)
            i+=step;
    return i;
}

int bs(vector<Dreapta> &v,int x,int y)
{
    int i,step=1<<9;
    for (i=0;step;step>>=1)
        if (i+step<v.size() && v[i+step].height(x)<=y)
            i+=step;
    if (v[i].height(x)==y)
        return 1;
    return i;
}

bool bs(vector<int> &v,int x)
{
    if (v.empty())
        return false;
    int i,step=1<<9;
    for (i=0;step;step>>=1)
        if (i+step<v.size() && v[i+step]<=x)
            i+=step;
    return v[i]==x || !(i&1);
}

void add(vector<int> &v,int x,int y)
{
    if (y<x)
        sch(x,y);
    v.push_back(x);
    v.push_back(y);
}

int main()
{
    int m,x,y,D=0,q;
    in>>n>>m;
    for (int i=1;i<=n;i++)
    {
        in>>poli[i].x>>poli[i].y;
        X[i]=poli[i].x;
    }
    poli[n+1]=poli[1];
    for (int i=1;i<=n;i++)
        if (poli[i].x!=poli[i+1].x)
            line[++nr].det(poli[i],poli[i+1]);
        else
            add(edge[poli[i].x],poli[i].y,poli[i+1].y);
    sort(X+1,X+n+1);
    X[0]=-1;
    for (int i=1;i<=n;i++)
        if (X[i]!=X[i-1])
            X[++D]=X[i];
    X[0]=D;
    for (int i=1;i<X[0];i++)
    {
        for (int j=1;j<=nr;j++)
            if (line[j].inside(X[i],X[i+1]))
                add(inter[i],line[j],X[i]);
        sort(inter[i].begin(),inter[i].end(),cmp);
    }
    while (m--)
    {
        in>>x>>y;
        q=bs(X,x);
        if (q==-1)
            continue;
        rez+=(bs(inter[q],x,y) & 1) | bs(edge[x],y);
    }
    out<<rez<<"\n";
    return 0;
}