Cod sursa(job #1155601)

Utilizator alexalghisiAlghisi Alessandro Paolo alexalghisi Data 27 martie 2014 00:41:26
Problema Poligon Scor 0
Compilator cpp Status done
Runda Lista lui wefgef Marime 4.35 kb
#include <iostream>
#include <vector>
#include <set>
#include <algorithm>
#include <fstream>


#define per pair<double,double>
#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;
    int A,B,C;
    double mij;
};

set < per > mpp;
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];
        mpp.insert( 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

        //int i = 2;
        /// 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[next_j];

                    /// ecuatia dreptei
                    p.A = (p.b.y - p.a.y);
                    p.B = -(p.b.x - p.a.x);
                    p.C = -p.a.x*(p.b.y - p.a.y) + p.a.y*( p.b.x - p.a.x);
                    /// intersectia cu banda devine
                    p.a.x = bucket[i].x;
                    p.a.y = -( p.A * p.a.x + p.C) / p.B;
                    p.b.x = bucket[i].y;
                    p.b.y = -( p.A * p.b.x + p.C) / p.B;

                    p.mij = (p.a.y + p.b.y)/2;

                    /*if( i == 2){
                        cout<<"LIM: "<<p.a.x<<" "<<p.a.y<<" | "<<p.b.x<<" "<<p.b.y<<endl;
                        cout<<"A : "<<p.A<<" B :" <<p.B<<" C:"<<p.C<<endl;
                    }*/

                    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);

    int max_y = max(line.a.y,line.b.y);

    per c;
    c.x = line.a.x;
    c.y = line.b.y;

    //cout<<line.a.x<<" "<<line.a.y<<" | "<<line.b.x<<" "<<line.b.y<<endl;
    //cout<<"REZ:"<< ( max_y <= p.y || in_tri(line.a,line.b,c,p) )<<endl;

    if( max_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])){

            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;
        if( mpp.find(p) != mpp.end()){ /// varf
            ++rez;
            continue;
        }
        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<<"punctul :"<<i<<" in bucketul:"<<bucket<<" si are sub el: "<<under<<endl;
    }
    g<<rez;
}

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

    return 0;
}