Cod sursa(job #896680)

Utilizator SebiSebiPirtoaca George Sebastian SebiSebi Data 27 februarie 2013 16:46:02
Problema Poligon Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.61 kb
#include<iostream>
#include<fstream>
#include<algorithm>
#include<vector>
using namespace std;

#define NMAX 802
#define pb push_back
#define mp make_pair
#define pair pair < int , int >
#define x first
#define y second

vector <pair> v,cb;
vector <int> b[NMAX];
int a[NMAX],aux[NMAX],ind;

inline double val(int i)
{
    double a,b,c;
    a=(double)(v[i].y-v[i+1].y);
    b=(double)(v[i+1].x-v[i].x);
    c=(double)(v[i].x*v[i+1].y-v[i+1].x*v[i].y);
    a=(double)((-a/b)*(cb[ind].y+cb[ind].x)/2-(c/b));
    return a;
}

inline bool cmp(const int &a, const int &b)
{
    return val(a)>val(b);
}

inline double cross_product(pair a, pair b, pair c)
{
     return (double)((b.x-a.x)*(c.y-a.y)-(c.x-a.x)*(b.y-a.y));
}

inline int cb1(int p, int q, int x)
{
    int mij;
    if(cb[p].x>x || cb[q].y<x)
        return -1;
    while(p<=q) {
        mij=(p+q)/2;
        if(cb[mij].x<=x && x<=cb[mij].y)
            return mij;
        if(cb[mij].y<x)
            p=mij+1;
        else if(cb[mij].x>x)
            q=mij-1;
    }
    return -1;
}

inline int cb2(int p, int q, int banda, pair x)
{
    int mij,r;
    ind=banda;
    if(cross_product(v[b[ind][1]],v[b[ind][1]+1],x)<0)
        return 0;
    while(p<=q) {
        mij=(p+q)/2;
        r=cross_product(v[b[ind][mij]],v[b[ind][mij]+1],x);
        if(r<0)
            q=mij-1;
        else if(r>0)
            p=mij+1;
        else return q-mij;
    }
    while(cross_product(v[b[ind][mij+1]],v[b[ind][mij+1]+1],x)>0 && mij<q)
        mij++;
    return mij;
}

int main ()
{
    int n,m,i,x,y,l,j,nr,sol;
    ifstream f("poligon.in");
    ofstream g("poligon.out");
    f>>n>>m;
    v.pb(mp(-1,-1));
    for(i=1;i<=n;i++) {
        f>>x>>y;
        v.pb(mp(x,y));
    }
    if(v[0].x>v[1].x || (v[0].x==v[1].x && v[0].y<v[1].y))
        reverse(v.begin()+1,v.end());
    v.pb(v[1]);
    aux[0]=-1;
    for(i=1;i<=n;i++)
        aux[i]=v[i].x;
    sort(aux+1,aux+n+1);
    l=0;
    cb.pb(mp(-1,-1));
    for(i=1;i<=n-1;i++) {
        if(aux[i]==aux[i-1])
            continue;
        cb.pb(mp(aux[i],aux[i+1]));
        l++;
        for(j=1;j<=n;j++)
            if(min(v[j].x,v[j+1].x)<=aux[i] && max(v[j].x,v[j+1].x)>=aux[i+1])
                b[l].pb(j);
    }
    for(i=1;i<=l;i++) {
        ind=i;
        sort(b[i].begin(),b[i].end(),cmp);
    }
    sol=0;
    for(i=1;i<=m;i++) {
        f>>x>>y;
        nr=cb1(1,l,x);
        if(nr!=-1) {
            if(cb2(0,b[nr].size()-1,nr,mp(x,y))%2==1)
                sol++;
        }
    }
    f.close();
    g<<sol;
    g.close();
    return 0;
}