Cod sursa(job #2148815)

Utilizator topala.andreiTopala Andrei topala.andrei Data 2 martie 2018 00:51:12
Problema Poligon Scor 50
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.86 kb
#include <iostream>
#include <fstream>
#include <cmath>

#define exterior -1
#define pe_latura 0
#define interior 1

using namespace std;
ifstream f("poligon.in");
ofstream g("poligon.out");
const int maxn = 805;
const double EPS = 1e-10;
int N, m;

struct punct
{
    double x, y;
};
punct P[maxn], M;

int int_pe_ext()
{
    int i, intersectii = 0;
    P[N + 1] = P[1];
    P[N + 2] = P[2];
    for(i = 1; i <= N; i++)
    {
        if((P[i].x < M.x && M.x < P[i + 1].x) || (P[i].x > M.x && M.x > P[i + 1].x))
        {
            double cy = P[i].y + (M.x - P[i].x) * (P[i].y - P[i + 1].y) / (P[i].x - P[i + 1].x);
            if(abs(M.y - cy) < EPS) return pe_latura;
            else
                if(M.y > cy) intersectii++;
            continue;
        }

        if(P[i].x == M.x)
        {
            if(P[i].y == M.y)
                return pe_latura;
            if((P[i+1].x ==M.x) && ((P[i].y <= M.y && M.y <= P[i + 1].y) || (P[i].y >= M.y && M.y >= P[i + 1].y)))
                return pe_latura;
        }

        if(P[i].x == M.x && P[i].y <= M.y)
        {
            if(P[i + 1].x == M.x)
            {
                if(M.y <= P[i + 1].y)
                    return pe_latura;
                else
                    if((P[i - 1].x - M.x) * (P[i + 2].x - M.x) <= 0)
                        intersectii++;
            }
            else
            {
                if((P[i - 1].x - M.x) * (P[i + 1].x - M.x) < 0)
                    intersectii++;
            }
        }
    }

    if(intersectii % 2 == 1) return interior;
    return exterior;
}
int main()
{
    int ans=0;
    f >> N >> m;
    for(int i = 1; i <= N; i++)
        f >> P[i].x >> P[i].y;
    for(int i = 1; i <= m; i++)
    {
        f >> M.x >> M.y;
        if(int_pe_ext() >= 0) ans++;
    }
    g<<ans<<'\n';

    return 0;
}