Cod sursa(job #2328762)

Utilizator buhaidarius@gmail.comBuhai Darius [email protected] Data 26 ianuarie 2019 10:34:40
Problema Poligon Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.05 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;
}p1[MAXN], p2, pext;

bool verif_in(point p){
    int nrint = 0;
    for(int i=0;i<n;i++){
        /// intersect p1[i] p1[j]
        int j = i+1;
        if(j==n) j=0;
        int d1 = (p.x*pext.y+pext.x*p1[i].y+p1[i].x*p.y)-(p1[i].x*pext.y+p1[i].y*p.x+p.y*pext.x);
        int d2 = (p.x*pext.y+pext.x*p1[j].y+p1[j].x*p.y)-(p1[j].x*pext.y+p1[j].y*p.x+p.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", &p1[i].x, &p1[i].y);
    for(int i=0;i<m;i++){
        scanf("%d %d\n", &p2.x, &p2.y);
        if(verif_in(p2))
            nrin++;
    }
    printf("%d", nrin);
    return 0;
}