Cod sursa(job #1306736)

Utilizator chiriacandrei25Chiriac Andrei chiriacandrei25 Data 31 decembrie 2014 14:38:41
Problema Poligon Scor 70
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.24 kb
#include <fstream>
#include <algorithm>
#include <vector>
#define Nmax 805

using namespace std;

struct Point
{
    long double x,y;
    bool operator <(const Point &A) const
    {
        return x<A.x;
    }
} a[Nmax],b[Nmax];

struct Segment
{
    Point a,b;
    bool operator <(const Segment &A) const
    {
        return max(a.y,b.y)>max(A.a.y,A.b.y);
    }
};
vector <Segment> L[Nmax];
Segment mat[Nmax][Nmax];
int n,len[Nmax];

inline bool Inter (int x, int y, int st, int dr)
{
    if(x<=st && y>=dr) return true;
    return false;
}

inline Point IntDr(Point A, Point B, Point C)
{
    Point sol;
    sol.x=C.x;
    sol.y=(A.x*B.y+A.y*C.x-B.x*A.y-B.y*C.x)/(A.x-B.x);
    return sol;
}

inline int Lower(Segment a[], int n, Point p)
{
    int st=1,dr=n,mij,sol=0;
    while(st<=dr)
    {
        mij=(st+dr)/2;
        Point w=IntDr(a[mij].a,a[mij].b,p);
        if(w.y>p.y)
        {
            sol=mij; st=mij+1;
        }
        else dr=mij-1;
    }
    return sol;
}

int main()
{
    int i,j,m,sol=0;
    Segment w;
    Point x,y,z,t,q;
    ifstream fin ("poligon.in");
    ofstream fout ("poligon.out");
    fin>>n>>m;
    for(i=1;i<=n;++i)
    {
        fin>>a[i].x>>a[i].y;
        b[i]=a[i];
    }
    sort(a+1,a+n+1);
    a[n+1]=a[1];
    b[n+1]=b[1];
    for(i=1;i<=n;++i)
    {
        if(a[i].x==a[i+1].x) continue;
        for(j=1;j<=n;++j)
            if(Inter(min(b[j].x,b[j+1].x),max(b[j].x,b[j+1].x),min(a[i].x,a[i+1].x),max(a[i].x,a[i+1].x)))
            {
                x=b[j]; y=b[j+1];
                if(x.x>y.x) swap(x,y);
                z=a[i]; t=a[i+1];
                if(z.x>t.x) swap(z,t);
                w.a=IntDr(x,y,z);
                w.b=IntDr(x,y,t);
                L[i].push_back(w);
            }
    }
    for(i=1;i<=n;++i) sort(L[i].begin(),L[i].end());
    for(i=1;i<=n;++i)
    {
        vector <Segment>::iterator it;
        for(it=L[i].begin();it!=L[i].end();++it) mat[i][it-L[i].begin()+1]=*it;
        len[i]=L[i].size();
    }
    while(m--)
    {
        fin>>q.x>>q.y;
        i=upper_bound(a+1,a+n+1,q)-a-1;
        if(!i) continue;
        if(Lower(mat[i],len[i],q)%2) ++sol;
    }
    fout<<sol<<"\n";
    return 0;
}