Cod sursa(job #2328932)

Utilizator buhaidarius@gmail.comBuhai Darius [email protected] Data 26 ianuarie 2019 11:31:56
Problema Poligon Scor 50
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.16 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;

long long det(point a, point b, point c)
{
    return (a.x*b.y+b.x*c.y+a.y*c.x)-(b.y*c.x+a.x*c.y+a.y*b.x);
}

bool verif_in(){
    int nrint = 0;
    for(int i=0;i<n;i++){
        point A = p[i], B = p[i+1];
        long long d1 = det(pint, A, B);
        long long d2 = det(pext, A, B);
        long long d3 = det(A, pint, pext);
        long long d4 = det(B, pint, pext);
        if(d1*d2<=0 && d3*d4<0)
            nrint++;
    }
    if(nrint%2==1)
        return true;
    return false;
}

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