Cod sursa(job #2328925)

Utilizator q1e123Solca Robert-Nicolae q1e123 Data 26 ianuarie 2019 11:29:37
Problema Poligon Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.34 kb
#include <cstdio>

const int N_MAX = 800;
const int M_MAX = 60000;

struct Punct{
    int x,y;
};


int n,m;
Punct poligon[N_MAX],infractiuni[M_MAX];
Punct E = {-1,-1};

void read(){
    scanf("%d %d",&n,&m);
  //  printf("%d %d\n",n,m);
    for(int i=0; i<n;++i){
        int x,y;
        scanf("%d %d",&x,&y);
        poligon[i].x = x;
        poligon[i].y = x;
    }

    for(int i=0; i<m;++i){
        int x,y;
        scanf("%d %d",&x,&y);
        infractiuni[i].x = x;
        infractiuni[i].y = x;
    }
}

long long determinant(Punct A,Punct B,Punct C){
    return 1LL*(B.x - A.x)*(C.y-A.y)-1LL*(C.x-A.x)*(B.y-A.y);
}

bool parte(Punct A,Punct B,Punct P){
    if(determinant(A,B,P)*determinant(A,B,E)<=0) return true;
    return false;
}

void solve(){
    int rez;
    rez =0;
    for(int i=0;i<m;++i){
        int intersectie;
        intersectie = 0;

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

            if(parte(poligon[j],poligon[j+1],infractiuni[i])){
                ++intersectie;
            }
        }
        if(parte(poligon[0],poligon[n-1],infractiuni[i])){
            ++intersectie;
        }
    //   printf("%d\n",intersectie);
        if(intersectie%2){
            ++rez;
        }
    }
    printf("%d",rez);
}

int main() {
    freopen("poligon.in","r",stdin);
    freopen("poligon.out","w",stdout);
    read();
    solve();
    return 0;
}