Cod sursa(job #2158474)

Utilizator Alexandru_StoianStoian Sorin Alexandru Alexandru_Stoian Data 10 martie 2018 13:18:10
Problema Poligon Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.63 kb
#include <iostream>
#include <fstream>
#include <algorithm>
#define inf 2147400000

using namespace std;

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

int n,M,x,y,nrpuncte;

double m;

struct poligon{
    int x,y;
    double m;
}A[801];

bool cmp(poligon a, poligon b){
    return a.m < b.m;
}

bool verif2(int x,int y,int mij){
    long long val1,val2,val3;
    val1=(A[mij].x*A[mij-1].y-A[mij].y*A[mij-1].x+A[mij-1].x*y-x*A[mij-1].y+x*A[mij].y-y*A[mij].x);
    val2=(A[1].x*A[mij].y-A[1].y*A[mij].x+A[mij].x*y-x*A[mij].y+x*A[1].y-y*A[1].x);
    val3=(A[mij-1].x*A[1].y-A[mij-1].y*A[1].x+A[1].x*y-x*A[1].y+x*A[mij-1].y-y*A[mij-1].x);
    if(val1<=0 && val2<=0 && val3<=0)return 1;
    if(val1>=0 && val2>=0 && val3>=0)return 1;
    return 0;
}
bool verif(int x, int y){
    int in,sf,mij;
    in=2;
    sf=n;
    if(x!=A[1].x)m=double(y-A[1].y)/double(x-A[1].x);
    else m=inf;
    if(m>=A[2].m && m<=A[n].m){
        while(in<=sf){
            mij=(in+sf)/2;
            if(m>=A[mij-1].m && m <= A[mij].m){
                in=sf+1;
            }
            else
                if(m<A[mij-1].m)sf=mij-1;
                else in=mij+1;

        }
        if(verif2(x,y,mij))return 1;
    }
    return 0;

}


int main(){
    f>>n>>M;\
    for(int i=1; i<=n; ++i)
        f>>A[i].x>>A[i].y;
    A[1].m=-inf;
    for(int i=2; i<=n; ++i)
        if(A[i].x != A[1].x)A[i].m=(A[i].y-A[1].y)/(A[i].x-A[1].x);
        else A[i].m=inf;
    sort(A+1, A+n+1, cmp);
    for(int i=1; i<=M; ++i){
        f>>x>>y;
        if(verif(x,y))++nrpuncte;
    }
    g<<nrpuncte<<'\n';
    return 0;
}