Cod sursa(job #474081)

Utilizator freak93Adrian Budau freak93 Data 2 august 2010 14:51:25
Problema Poligon Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.18 kb
#include<fstream>
#include<algorithm>
#include<vector>

using namespace std;

const char iname[]="poligon.in";
const char oname[]="poligon.out";
const int maxn=905;

ifstream f(iname);
ofstream g(oname);

struct point
{
    int x,y;
    point():x(0),y(0){}
    point(int _x,int _y):x(_x),y(_y){}
} a[maxn];

bool operator<(const point& a,const point &b)
{
    if(a.x==b.x)
        return a.y<b.y;
    return a.x<b.x;
}

long long area(point a,point b,point c)
{
    return 1LL*a.x*(b.y-c.y)+1LL*b.x*(c.y-a.y)+1LL*c.x*(a.y-b.y);
}

long long area(point a,point b,point c,point d)
{
    return 1LL*a.x*(b.y-d.y)+1LL*b.x*(c.y-a.y)+1LL*c.x*(d.y-b.y)+d.x*(a.y-c.y);
}

int n,i,j,k,m,v[maxn];
vector<int> E[maxn];

bool fcomp(int x,int y)
{
    return area(min(a[x],a[x+1]),max(a[x],a[x+1]),max(a[y+1],a[y]),min(a[y],a[y+1]))>=0;
}

int main()
{
    f>>n;
    for(i=1;i<=n;++i)
        f>>a[i].x>>a[i].y,v[i]=a[i].x;
    a[n+1]=a[1];
    v[n+1]=-1;
    v[n+2]=60001;
    sort(v+1,v+n+3);
    k=(unique(v+1,v+n+3)-v);

    for(i=1;i<=n;++i)
        for(j=0;j<k;++j)
            if(a[i].x<=v[j]&&a[i+1].x>=v[j+1])
                E[j].push_back(i);

    for(i=0;i<k;++i)
        sort(E[i].begin(),E[i].end(),fcomp);


}