Cod sursa(job #2330180)

Utilizator maria_sinteaMaria Sintea maria_sintea Data 27 ianuarie 2019 23:45:34
Problema Poligon Scor 50
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.04 kb
#include <iostream>
#include <cstdio>
#define N 805
#define inf 0x3f3f3f3f

using namespace std;

struct punct
{
    int x, y;
}a, p[N], b;
int n, nr, m;

void citire()
{
    scanf("%d %d\n", &n, &m);
    for(int i=0;i<n;i++)
    {
        scanf("%d %d\n", &p[i].x, &p[i].y);
    }
    b={88069, 87803};
    p[n]=p[0];
}

long long f(punct a, punct b, punct c)
{
    return (b.x-a.x)*(c.y-a.y)-(b.y-a.y)*(c.x-a.x);
}

int intersectii()
{
    int nr=0;
    for(int i=0;i<n;i++)
    {
        long long f1=f(a, p[i], p[i+1]);
        long long f2=f(b, p[i], p[i+1]);
        long long f3=f(p[i], a, b);
        long long f4=f(p[i+1], a, b);
        if(f1*f2<=0 && f3*f4<0)
            nr++;
    }
    return nr;
}

int main()
{
    freopen("poligon.in", "r", stdin);
    freopen("poligon.out", "w", stdout);

    citire();
    for(int i=0;i<m;i++)
    {
        scanf("%d %d\n", &a.x, &a.y);
        int num=intersectii();
        if(num%2==1)
            nr++;
    }
    printf("%d\n", nr);
    return 0;
}