Cod sursa(job #1211640)

Utilizator mirceadinoMircea Popoveniuc mirceadino Data 22 iulie 2014 22:58:58
Problema Poligon Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 4.42 kb
#include<iostream>
#include<fstream>
#include<vector>
#include<algorithm>
#include<cstdio>

using namespace std;

const int NMAX = 800+5;
const int MMAX = 60000+6;
const int INF = (1<<30);

ifstream fin("poligon.in");
ofstream fout("poligon.out");

struct point
{
    double x,y;

    inline point()
    {

    }

    inline point(double _x,double _y)
    {
        x=_x;
        y=_y;
    }

    inline bool operator()(const point &A,const point &B) const
    {
        return A.x<B.x;
    }
};

inline int crossProd(point A,point B,point C)
{
    if ((A.x-C.x)*(B.y-C.y)-(A.y-C.y)*(B.x-C.x)>0) return 1;
    else if ((A.x-C.x)*(B.y-C.y)-(A.y-C.y)*(B.x-C.x)<0) return -1;
    else return 0;
}

struct side
{
    point A,B;
    double m,n,y;

    inline side()
    {

    }

    inline side(point _A,point _B)
    {
        A=_A;
        B=_B;
        if(A.x-B.x)
        {
            m=(A.y-B.y)/(A.x-B.x);
            n=A.y-m*A.x;
            if(A.x>B.x) swap(A,B);
        }
        else
        {
            m=INF;
            n=A.x;
            if(A.y>B.y) swap(A,B);
        }
        y=(A.y+B.y)/2.0;

    }

    inline point pointOnSide(double x)
    {
        return point(x,m*x+n);
    }

    inline bool pointOn(point X)
    {
        if(m==INF)
        {
            if(X.x==n) return (X.y>=A.y && X.y<=B.y);
            return 0;
        }
        if(A.x<=X.x && X.x<=B.x && A.y<=X.y && X.y<=B.y) return crossProd(A,B,X)==0;
        return 0;
    }

    inline bool operator()(const side &AB,const side &MN) const
    {
        if(AB.m==INF && MN.m==INF) return AB.n<MN.n;
        else if(AB.m==INF || MN.m==INF) return 0;
        else return AB.y<MN.y;
    }
};

struct region
{
    int x,y;
    vector<side> V;

    inline region()
    {

    }

    inline region(int _x,int _y)
    {
        x=_x;
        y=_y;
        V.resize(0);
    }

    inline void add(side AB)
    {
        if(AB.m==INF) V.push_back(AB);
        else V.push_back(side(AB.pointOnSide(x),AB.pointOnSide(y)));
    }

    inline void sortSides()
    {
        sort(V.begin(),V.end(),side());
    }
};

int N,M,cnt,sol;
point P[NMAX];
side S[NMAX];
vector<side> verticalSides;
region R[NMAX];

inline bool intersection(int a,int b,int c,int d) // [a,b) ^ [c,d)
{
    return max(a,c)<=min(b-1,d-1);
}

inline void increaseSolution()
{
    sol++;
}

int main()
{
    int i,j,k,x,y;

    fin>>N>>M;

    for(i=1; i<=N; i++)
    {
        fin>>x>>y;
        P[i]=point(x,y);
    }

    P[N+1]=P[1];

    for(i=1; i<=N; i++)
    {
        S[i]=side(P[i],P[i+1]);
        if(S[i].m==INF) verticalSides.push_back(S[i]);
    }

    sort(verticalSides.begin(),verticalSides.end(),side());

    sort(P+1,P+N+1,point());

    for(j=1,i=2; i<=N; i++)
    {
        if(P[i-1].x!=P[i].x)
        {
            R[++cnt]=region(P[j].x,P[i].x);
            for(k=1; k<=N; k++)
                if(intersection(S[k].A.x,S[k].B.x,P[j].x,P[i].x)) R[cnt].add(S[k]);
            j=i;
            R[cnt].sortSides();
            continue;
        }
    }

    int lo,hi,mi,pssy,val;
    point T;

    return 0;

    while(M--)
    {
        fin>>x>>y;

        T=point(x,y);

        lo=1,hi=cnt;

        while(lo<=hi)
        {
            mi=(lo+hi)/2;
            if(R[mi].x<=x && x<=R[mi].y) break;
            if(R[mi].x>x) hi=mi-1;
            if(R[mi].y<x) lo=mi+1;
        }

        if(lo<=hi)
        {
            i=mi;
            lo=0,hi=R[i].V.size()-1;

            pssy=0;

            while(lo<=hi)
            {
                mi=(lo+hi)/2;
                val=crossProd(R[i].V[mi].A,R[i].V[mi].B,T);
                if(val>0)
                {
                    pssy=mi+1;
                    lo=mi+1;
                }
                if(val<0) hi=mi-1;
                if(val==0) {pssy=1; break;}
            }

            if(pssy%2) increaseSolution();

            continue;
        }

        lo=0,hi=verticalSides.size()-1;

        while(lo<=hi)
        {
            mi=(lo+hi)/2;
            if(verticalSides[mi].n==x && verticalSides[mi].pointOn(T))
            {
                increaseSolution();
                break;
            }
            if(verticalSides[mi].n<x) lo=mi+1;
            if(verticalSides[mi].n>x) hi=mi-1;
        }
    }

    fout<<sol<<'\n';

    return 0;
}