Cod sursa(job #2148818)

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

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

using namespace std;
FILE*f=freopen("poligon.in","r",stdin);
FILE*g=freopen("poligon.out","w",stdout);
const int maxn = 805;

const double EPS = 1e-10;
int N, m, pos;
char buff[290001];

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

void citire(int &nr)
{
    while(buff[pos] < '0' || buff[pos] > '9') if(++pos == 290000) fread(buff, 1, 290000, stdin), pos = 0;
    nr = 0;
    while('0' <= buff[pos] && buff[pos] <= '9')
    {
        nr = nr * 10 + buff[pos] - '0';
        if(++pos == 290000) fread(buff, 1, 290000, stdin), pos = 0;
    }
}

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,x;
    citire(N);
    citire(m);

    for(int i = 1; i <= N; i++)
    {
        citire(x);
        P[i].x=x;

        citire(x);
        P[i].y=x;
    }
    for(int i = 1; i <= m; i++)
    {
        citire(x);
        M.x=x;

        citire(x);
        M.y=x;

        if(int_pe_ext() >= 0) ans++;
    }

    printf("%d\n",ans);
    return 0;
}