Cod sursa(job #2404809)

Utilizator david.sachelarieDavid Sachelarie david.sachelarie Data 13 aprilie 2019 13:53:32
Problema Poligon Scor 50
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.28 kb
#include <iostream>
#include <fstream>

using namespace std;

int v[800][2];

double verifyCrossing(int i,int a,int &dir_crossed,int n){
    double y;
    int j=(i+1)%n;
    dir_crossed=-1;

    if(v[i][0]==v[j][0])
        return -1;

    y=((double)a-(double)v[i][0])*((double)v[j][1]-(double)v[i][1])/((double)v[j][0]-(double)v[i][0])+(double)v[i][1];
    if((y==v[i][1] && v[i][0]<v[j][0]) || (y==v[j][1] && v[j][0]<v[i][0])){
        dir_crossed=1;
        return y;

    }
    else if((y==v[i][1] && v[i][0]>v[j][0]) || (y==v[j][1] && v[j][0]>v[i][0])){
        dir_crossed=2;
        return y;
    }
    else if((y>v[i][1] && y<v[j][1] && v[i][1]<v[j][1]) || (y>v[j][1] && y<v[i][1] && v[j][1]<v[i][1])){
        return y;
    }
    else{
        return -1;
    }
}

int seeIfInside(int a,int b,int n){
    int dir_trecut=-1,dir_first;
    int dir_crossed;
    int bigger=0,smaller=0;
    double y;
    double first,trecut=-1;

    int i;
    for(i=0;i<n;i++){
        y=verifyCrossing(i,a,dir_crossed,n);
        if(i==0){
            first=y;
            dir_first=dir_crossed;
        }
        if(y!=-1 && (dir_crossed==-1 || (dir_crossed!=-1 && trecut!=y))){
            if(y==b)
                return 1;
            else if(y>b)
                bigger++;
            else
                smaller++;
        }
        else if(y!=-1 && dir_crossed!=-1 && trecut==y && dir_crossed==dir_trecut){
            if(y==b)
                return 1;
            else if(y>b)
                bigger--;
            else
                smaller--;
        }
        dir_trecut=dir_crossed;
        trecut=y;
    }
    trecut=first;
    dir_crossed=dir_first;
    if(y!=-1 && dir_crossed!=-1 && trecut==y && dir_crossed==dir_trecut){
        if(y==b)
            return 1;
        else if(y>b)
            bigger-=2;
        else
            smaller-=2;
    }

    if(bigger%2==1) return 1;
    else return 0;
}

int main()
{
    ifstream fin("poligon.in");
    ofstream fout("poligon.out");

    int n,m;
    fin>>n>>m;

    int i;
    for(i=0;i<n;i++)
        fin>>v[i][0]>>v[i][1];

    int a,b;
    int nr=0;
    for(i=0;i<m;i++){
        fin>>a>>b;
        nr+=seeIfInside(a,b,n);
    }

    fout<<nr<<"\n";
    return 0;
}