Cod sursa(job #990272)

Utilizator poptibiPop Tiberiu poptibi Data 27 august 2013 20:29:32
Problema Poligon Scor 80
Compilator cpp Status done
Runda Lista lui wefgef Marime 2.31 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;
vector<int> Strip[810];
int OnEdge;

struct Comp
{
    bool operator() (int Idx1, int Idx2)
    {
        return (-(1.0 * A[Idx1] / B[Idx1]) * (Left + Right) - (2.0 * C[Idx1] / B[Idx1]) < -(1.0 * A[Idx2] / B[Idx2]) * (Left + Right) - (2.0 * C[Idx2] / B[Idx2]));
    }
};

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

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

    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 = 2048; Step; Step /= 2)
            if(GoodStrip + Step <= X[0] && X[GoodStrip + Step] < P.X)
                GoodStrip += Step;

        for(int Step = 2048; 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;
}