Cod sursa(job #486831)

Utilizator freak93Adrian Budau freak93 Data 22 septembrie 2010 21:08:21
Problema Gradina Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.38 kb
#include<fstream>
#include<algorithm>
#include<string>

using namespace std;

const char iname[]="gradina.in";
const char oname[]="gradina.out";
const int maxn=256;

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

struct point
{
    int x,y,z;
    bool operator<(const point& v) const
    {
        if(x!=v.x)
            return x<v.x;
        return y<v.y;
    }
} a[maxn],b[maxn],c[maxn];

int n,i,j,k,p,q,x,y,mint,stiva[maxn],used[maxn];
string aux,rez;

int arry(point a,point b,point c)
{
    return a.x*(b.y-c.y)+b.x*(c.y-a.y)+c.x*(a.y-b.y);
}

int chull(point a[],int n)
{
    if(n<3)
        return 0;
    stiva[0]=1;
    stiva[1]=2;
    memset(used,0,sizeof(used));
    int i=2,k=1,stp=1;
    used[2]=1;
    while(used[1]==0)
    {
        if(i==n)
            stp=-1;
        while(used[i]==1)
            i+=stp;
        while(k&&arry(a[stiva[k-1]],a[stiva[k]],a[i])>0)
            used[stiva[k--]]=0;
        used[stiva[++k]=i]=1;
    }
    int area=0;
    if(k!=n)
        return 0;
    for(i=1;i<=k;++i)
        area+=a[stiva[i-1]].x*a[stiva[i]].y-a[stiva[i]].x*a[stiva[i-1]].y;
    return max(area,-area);
}

int main()
{
    f>>n;
    for(i=1;i<=n;++i)
        f>>a[i].x>>a[i].y,a[i].z=i;
    sort(a+1,a+n+1);
    mint=(1<<31)-1;
    aux.resize(n);
    for(i=1;i<=n;++i)
        for(j=1;j<=n;++j)
            if(i!=j)
            {
                p=q=0;
                for(k=1;k<=n;++k)
                    if(k-i&&k-j)
                        if(arry(a[i],a[j],a[k])>0)
                            b[++p]=a[k];
                        else
                            c[++q]=a[k];
                    else
                        if(k==i)
                            b[++p]=a[k];
                        else
                            c[++q]=a[k];
                x=chull(b,p);
                y=chull(c,q);
                if(x&&y)
                    if(max(x-y,y-x)<=mint)
                    {
                        for(k=1;k<=p;++k)
                            aux[b[k].z-1]='I';
                        for(k=1;k<=q;++k)
                            aux[c[k].z-1]='V';
                        if(max(x-y,y-x)==mint)
                            rez=min(rez,aux);
                        else
                            rez=aux;
                        mint=max(x-y,y-x);
                    }
            }

    g.setf(ios::fixed,ios::floatfield);
    g.precision(1);
    g<<(double)mint/2.0<<"\n";
    g<<rez<<"\n";
}