Cod sursa(job #1197900)

Utilizator ZenusTudor Costin Razvan Zenus Data 14 iunie 2014 00:57:12
Problema Poligon Scor 100
Compilator cpp Status done
Runda Lista lui wefgef Marime 3.37 kb
#include <cstdio>
#include <algorithm>
#include <utility>
#include <vector>

using namespace std;

#define NMAX 850
#define VMAX 60001
#define Dif 0.0000001
#define LL long long

pair < int , int > P[NMAX];
struct line
{
    int a;
    int b;
    LL c;
}
Equation[NMAX];
vector < int > L[NMAX];
double OX_Equation[NMAX];
double OY_Equation[NMAX];
bool sel[VMAX];
int B[NMAX];
int now_B,N,M,sol;

int get(int X)
{
    int Left,Right,Mid;

    Left=0,Right=B[0]+1;

    while (Right>Left+1)
    {
        Mid=(Left+Right)/2;

        (B[Mid]<=X) ? Left=Mid : Right=Mid;
    }

    return Left;
}

double Y_get(int X,int Y)
{
    return OY_Equation[X]*Y/2.0+OX_Equation[X];
}

bool cmp(int X,int Y)
{
    int Mid;
    double Y1,Y2;

    Mid=B[now_B]+B[now_B+1];

    Y1=Y_get(X,Mid);
    Y2=Y_get(Y,Mid);

    return Y2-Y1>Dif;

}

int solve()
{
    int X,Y,nowB,Left,Right,Mid,cnt;
    LL D;

    scanf("%d%d",&X,&Y);

    if (X<B[1] || X>B[B[0]]) return 0;

    now_B=get(X);

    if (now_B==B[0])
    {
        if (sel[Y]) return 1;
        return 0;
    }

    Left=-1,Right=L[now_B].size();

    while (Right>Left+1)
    {
        Mid=(Right+Left)/2;
        cnt=L[now_B][Mid];

        D=1LL*Equation[cnt].a*X + 1LL*Equation[cnt].b*Y + Equation[cnt].c;

        if (!D) return 1;

        (D>0) ? Left=Mid : Right=Mid;
    }

    ++Left;

    if (Left&1)
    return 1;

    return 0;
}

void lines_select()
{
    int i,up_lim,down_lim,j;

    for (i=1;i<=N;++i)
    if (max(P[i].first,P[i+1].first)==B[B[0]])
    {
        if (min(P[i].first,P[i+1].first)==B[B[0]])
        {
            up_lim=max(P[i].second,P[i+1].second);
            down_lim=min(P[i].second,P[i+1].second);

            for (j=down_lim;j<=up_lim;++j)
            sel[j]=true;
        }
        else (P[i].first==B[B[0]]) ? sel[P[i].second]=true : sel[P[i+1].second]=true;
    }
}

void Read()
{
    int i;

    scanf("%d%d",&N,&M);

    for (i=1;i<=N;++i)
    {
        scanf("%d%d",&P[i].first,&P[i].second);
        B[i]=P[i].first;
    }
    P[N+1]=P[1];

    sort(B+1,B+N+1);

    B[0]=1;
    for (i=2;i<=N;++i)
    {
        if (B[i]==B[B[0]]) continue;
        B[++B[0]]=B[i];
    }
}

void build_lines()
{
    int i,j;

    for (i=1;i<=B[0];++i)
    {
        for (j=1;j<=N;++j)
        {
            if (min(P[j].first,P[j+1].first)>B[i]) continue;
            if (B[i]>=max(P[j].first,P[j+1].first)) continue;
            L[i].push_back(j);
        }

        now_B=i;
        sort(L[i].begin(),L[i].end(),cmp);
    }
}

void build_Equations()
{
    int i,sgn1,sgn2;

    for (i=1;i<=N;++i)
    {
        (P[i].first<P[i+1].first) ? sgn1=1: sgn1=-1;
        sgn2=-sgn1;

        Equation[i].a=sgn1*P[i].second + sgn2*P[i+1].second;
        Equation[i].b=sgn1*P[i+1].first + sgn2*P[i].first;
        Equation[i].c=1LL*sgn1*P[i].first*P[i+1].second + 1LL*sgn2*P[i].second*P[i+1].first;

        OY_Equation[i]=(-1.0*Equation[i].a)/(1.0*Equation[i].b);
        OX_Equation[i]=(-1.0*Equation[i].c)/(1.0*Equation[i].b);
    }
}

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

    Read();

    build_Equations();

    build_lines();

    lines_select();

    while (M--)
    sol+=solve();

    printf("%d\n",sol);

    return 0;
}