Cod sursa(job #1754080)

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

#define MAX 60000
#define NMax 801
using namespace std;
ifstream f("poligon.in");
ofstream g("poligon.out");
struct point{
    int x,y;
};

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

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

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

        int odd = 0;

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

            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;
}