Cod sursa(job #1156725)

Utilizator alexalghisiAlghisi Alessandro Paolo alexalghisi Data 27 martie 2014 22:16:51
Problema Poligon Scor 30
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.89 kb
#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#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;
    double A,B,C;
    double mij;
};

bool on_border;
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

        //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];
                    if(p.a.x > p.b.x)
                        swap(p.a,p.b);

                    /// 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) * 0.5;



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

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

        if(is_less(p,mij))
            dr = mij - 1;
        else
            st = mij + 1;
    }
    return -1;
}

double fct( per p, st line){


   // if( y_dreapta == p.y )
      //  on_border = true;

    double tmp = line.A * p.x + line.B * p.y + line.C;

    /*cout<<line.a.x<<" "<<line.a.y<<" | "<<line.b.x<<" "<<line.b.y<<endl;
    cout<<"A : "<<line.A<<" B:"<<line.B<<" "<<line.C<<endl;
    cout<< tmp <<endl;*/

    return tmp ;

}


int find_under( per p, int ind){


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

    while(st<=dr){

        int mij = (st+dr)>>1;

        if( fct(p,banda[ind][mij - 1]) < 0 ){

            st = mij + 1;
            rez = mij;
        }
        else
        if( fct(p,banda[ind][mij - 1]) > 0)
            dr = mij - 1;
            else
                return 1; /// e pe dreatpa
    }
    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;
        on_border = false;

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

        int under = find_under(p,bucket);
        if(on_border == true || under%2 == 1)
            ++rez;

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

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

    return 0;
}