Cod sursa(job #2328783)

Utilizator buhaidarius@gmail.comBuhai Darius [email protected] Data 26 ianuarie 2019 10:43:53
Problema Poligon Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.08 kb
//
//  main.cpp
//  Poligon
//
//  Created by Darius Buhai on 26/01/2019.
//  Copyright © 2019 Darius Buhai. All rights reserved.
//

#include <iostream>
#include <cstdio>

#define MAXC 60001
#define MAXN 801
using namespace std;

int n, m, nrin;
struct point{
    int x, y;
}p[MAXN], pint, pext;

bool verif_in(point pint){
    int nrint = 0;
    for(int i=0;i<n;i++){
        /// intersect p[i] p[j]
        int j = i+1;
        if(j==n) j=0;
        int d1 = (pint.x*pext.y+pext.x*p[i].y+p[i].x*pint.y)-(p[i].x*pext.y+p[i].y*pint.x+pint.y*pext.x);
        int d2 = (pint.x*pext.y+pext.x*p[j].y+p[j].x*pint.y)-(p[j].x*pext.y+p[j].y*pint.x+pint.y*pext.x);
        if(d1*d2<0) nrint++;
    }
    return (bool)nrint%2;
}

int main() {
    freopen("poligon.in", "r", stdin);
    freopen("poligon.out", "w", stdout);
    pext = {MAXC, MAXC};
    scanf("%d %d\n", &n, &m);
    for(int i=0;i<n;i++)
        scanf("%d %d\n", &p[i].x, &p[i].y);
    for(int i=0;i<m;i++){
        scanf("%d %d\n", &pint.x, &pint.y);
        if(verif_in(pint))
            nrin++;
    }
    printf("%d\n", nrin);
    return 0;
}