Cod sursa(job #1155449)

Utilizator alexalghisiAlghisi Alessandro Paolo alexalghisi Data 26 martie 2014 22:05:02
Problema Poligon Scor 0
Compilator cpp Status done
Runda Lista lui wefgef Marime 3.36 kb
#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>
#include <fstream>


#define per pair<int,int>
#define mp make_pair
#define x first
#define y second
#define DN 805
using namespace std;

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

struct st{

    per a,b;
    double mij;
};


int n,m,rez;
per pol[DN],pol_initial[DN],bucket[DN];
vector < st > banda[DN];


void read(){

    f>>n>>m;
    for(int i=1;i<=n;++i){

        f>>pol[i].x>>pol[i].y;
        pol_initial[i] = pol[i];
    }
}

bool se_intersect(per a,per b,per c,per d){

    if(a.x > d.x)
        swap(a,d);
    if(a.x<=b.x && c.x<=d.x)
        return true;
    return false;
}

bool cmp(st a,st b){

    return a.mij < b.mij;
}

void prec(){ /// precalculare

    for(int i=1;i<n;++i){ /// pentru fiecare banda

        /// banda e determinata de : [pol[i].x , pol[i+1].x]
        bucket[i] = mp( pol[i].x , pol[i+1].x );

       // cout<<"Banda :"<<i<<" "<<i+1<<" ST:"<<pol[i].x<<" DR :"<<pol[i+1].x<<endl;

        for(int j=1 ; j<=n ; ++j){

                int next_j = j + 1;
                if(next_j > n)
                    next_j -=n;

                if(se_intersect(pol_initial[j],pol[i],pol[i+1],pol_initial[ next_j ])){

                   // cout<<j<<" "<<next_j<<endl;
                   // cout<<"x_st :"<<pol_initial[j].x<<" x_dr :"<<pol_initial[next_j].x<<endl;

                    st p;
                    p.a = pol_initial[j];
                    p.b = pol_initial[j+1];
                    p.mij = (p.a.y + p.b.y)/2;
                    banda[i].push_back(p);
                }
        }
        sort(banda[i].begin(),banda[i].end(),cmp);
    }

}
bool is_inside(per p,int ind){

    return (bucket[ind].x <= p.x && p.x <= bucket[ind].y);
}

bool is_less(per p,int ind){

    return ( p.x < bucket[ind].x );
}


int find_bucket( per p ){

    int st = 1 , dr = n - 1 ;
    while( st<=dr ){

        int mij = (st+dr)/2;

        if(is_inside(p,mij))
            return mij;

        if(is_less(p,mij))
            dr = mij - 1;
        else
            st = mij + 1;
    }
    return -1;
}
double arie(per a,per b,per c){

    int dx = a.x*b.y + b.x*c.y + a.y*c.x;
    int dy = c.x*b.y + b.x*a.y + c.y*a.x;
    return abs(dx-dy);
}


bool in_tri(per a,per b,per c,per x){

    if( arie(a,b,c) == arie(a,b,x) + arie(b,x,c) + arie(a,x,c))
        return true;
    return false;
}

bool is_under( per p, st line){

    if( line.a.y > line.b.y )
        swap(line.a,line.b);
    per c;
    c.x = line.b.x;
    c.y = line.a.y;

    if(c.y < p.y && !in_tri(line.a,line.b,c,p))
        return true;
    return false;
}


int find_under( per p, int ind){

    int st = 1 , dr = banda[ind].size(), rez = 0;

    while(st<=dr){

        int mij = (st+dr)/2;

        if( is_under(p,banda[ind][mij - 1])){

           //cout<<"DA"<<" :"<<mij-1<<"\n";

            st = mij + 1;
            rez = mij;
        }else
            dr = mij - 1;
    }
    return rez;
}

void solve(){

    sort(pol+1,pol+n+1);
    prec();
    for(int i=1;i<=m;++i){

        per p;
        f>>p.x>>p.y;

        int bucket = find_bucket(p);
        if( bucket == -1) continue; /// nu face parte din nicio banda

        int under = find_under(p,bucket);
        rez+=(under%2);

        //cout<<"iunctul :"<<i<<" in bucketul:"<<bucket<<" si are sub el: "<<under<<endl;
    }
    g<<rez;
}

int main()
{
    read();
    solve();

    return 0;
}