Cod sursa(job #1754085)

Utilizator VladTiberiuMihailescu Vlad Tiberiu VladTiberiu Data 7 septembrie 2016 15:42:56
Problema Poligon Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.31 kb
#include <bits/stdc++.h>

#define MAX 60000
#define NMax 801
using namespace std;
ifstream f("poligon.in");
ofstream g("poligon.out");

struct point{
    long long x,y;
};

point a[NMax];
long long n,m,A,B,ans;
long double x,y,fixed_x,fixed_y;

int main()
{
    f >> n >> m;
    for(long long i = 1; i <= n; ++i){
        f >> a[i].x >> a[i].y;
    }
    for(long long i = 1; i <= m; ++i){
        f >> x >> y;
        fixed_x = x + MAX;
        fixed_y = y + MAX + 1;

        long double aU = y - fixed_y;
        long double bU = fixed_x - x;
        long double cU = x * fixed_y - y * fixed_x;

        long long odd = 0;

        for(long long count = 1; count <= n; ++count){
            if(count == n){
                A = n; B = 1;
            }else{
                A = count; B = count + 1;
            }
            long double aD = a[A].y - a[B].y;
            long double bD = a[B].x - a[A].x;
            long double cD = a[A].x * a[B].y - a[A].y * a[B].x;

            long double int_x = (bD*cU - bU*cD) / (aD*bU - aU*bD);
            if(int_x >= min(a[A].x, a[B].x) && int_x <= max(a[A].x, a[B].x)){
                ++odd;
                odd %= 2;
            }
        }

        if(odd){
            ++ans;
        }
    }
    g << ans << '\n';
    return 0;
}