Cod sursa(job #990286)

Utilizator poptibiPop Tiberiu poptibi Data 27 august 2013 20:45:03
Problema Poligon Scor 100
Compilator cpp Status done
Runda Lista lui wefgef Marime 2.46 kb
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <vector>
#include <algorithm>
using namespace std;

#define X first
#define Y second

pair<int, int> V[810], P;
int S[810], X[810], A[810], B[810], C[810], Ans, N, M, Left, Right;
double CompactA[810], CompactC[810];
vector<int> Strip[810];
int OnEdge;

struct Comp
{
    bool operator() (int Idx1, int Idx2)
    {
        return (CompactA[Idx1] * (Left + Right) + 2 * CompactC[Idx1] < CompactA[Idx2] * (Left + Right) + 2 * CompactC[Idx2]);
    }
};

bool Check(int Index, pair<int, int> Point)
{
    if(A[Index] * Point.X + B[Index] * Point.Y + C[Index] == 0) OnEdge = 1;
    if(B[Index] >= 0) return A[Index] * Point.X + B[Index] * Point.Y + C[Index] >= 0;
    else return A[Index] * Point.X + B[Index] * Point.Y + C[Index] <= 0;
}

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

    scanf("%i %i", &N, &M);
    for(int i = 1; i <= N; ++ i)
        scanf("%i %i", &V[i].X, &V[i].Y);
    V[N + 1] = V[1];

    for(int i = 1; i <= N; ++ i)
        S[i] = V[i].X;

    sort(S + 1, S + N + 1);
    X[++ X[0]] = S[1];
    for(int i = 2; i <= N; ++ i)
        if(S[i] != S[i - 1])
            X[++ X[0]] = S[i];

    for(int i = 1; i <= N; ++ i)
    {
        A[i] = (V[i + 1].Y - V[i].Y);
        B[i] = (V[i].X - V[i + 1].X);
        C[i] = (V[i].Y * V[i + 1].X - V[i].X * V[i + 1].Y);
        CompactA[i] = -1.0 * A[i] / B[i];
        CompactC[i] = -1.0 * C[i] / B[i];
    }

    for(int i = 1; i <= X[0]; ++ i)
    {
        Left = X[i];
        Right = X[i + 1];
        for(int j = 1; j <= N; ++ j)
            if(min(V[j].X, V[j + 1].X) <= X[i] && X[i] < max(V[j].X, V[j + 1].X))
                Strip[i].push_back(j);
        sort(Strip[i].begin(), Strip[i].end(), Comp());
    }

    for(int i = 1; i <= M; ++ i)
    {
        scanf("%i %i", &P.X, &P.Y);
        if(!(X[1] <= P.X && P.X <= X[X[0]])) continue;

        int GoodStrip = 0, CntUnder = 0;
        OnEdge = 0;
        for(int Step = 1024; Step; Step /= 2)
            if(GoodStrip + Step <= X[0] && X[GoodStrip + Step] < P.X)
                GoodStrip += Step;

        for(int Step = 1024; Step; Step /= 2)
            if(CntUnder + Step <= Strip[GoodStrip].size() && Check(Strip[GoodStrip][CntUnder + Step - 1], P))
                CntUnder += Step;

        if(OnEdge || CntUnder % 2 == 1) Ans ++;
    }

    printf("%i\n", Ans);
    return 0;
}