Cod sursa(job #475328)

Utilizator ionutz32Ilie Ionut ionutz32 Data 6 august 2010 17:02:40
Problema Gradina Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 6.48 kb
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <bitset>

using namespace std;

int n,i,xmin,ymin,x,y,j,k,v1[255],v2[255],p,q,pct1,pct2,stack[255],nrs,io;
double a,b,s1,s2,sol;
bitset<255> exista,rez,nou;
pair<int,int> v[255];

inline bool egal(double a,double b)
{
    return (abs(a-b)<0.000000000001);
}

inline double dist(pair<int,int> a,pair<int,int> b)
{
    return sqrt((a.first-b.first)*(a.first-b.first)+(a.second-b.second)*(a.second-b.second));
}

struct cmp
{
    inline bool operator()(const int &a,const int &b)const
    {
        if (v[a].first==x && v[a].second==y)
            return 1;
        if (v[b].first==x && v[b].second==y)
            return 0;
        if (v[a].first==x)
            return 0;
        if (v[b].first==x)
            return 1;
        if (egal((double)(y-v[a].second)/(x-v[a].first),(double)(y-v[b].second)/(x-v[b].first)))
            return (dist(make_pair(x,y),v[a])<dist(make_pair(x,y),v[b]));
        return ((double)(y-v[a].second)/(x-v[a].first)<(double)(y-v[b].second)/(x-v[b].first));
    }
};

inline bool scoate(int vect[])
{
    if (v[vect[stack[nrs]]].first==v[vect[stack[nrs-1]]].first)
        return (v[vect[stack[1]]].first<v[vect[stack[nrs]]].first && v[vect[stack[nrs]]].first<v[vect[stack[k]]].first);
    double a,b,val1,val2;
    a=(double)(v[vect[stack[nrs]]].second-v[vect[stack[nrs-1]]].second)/(v[vect[stack[nrs]]].first-v[vect[stack[nrs-1]]].first);
    b=v[vect[stack[nrs]]].second-a*v[vect[stack[nrs-1]]].first;
    val1=a*v[vect[stack[1]]].first+b-v[vect[stack[1]]].second;
    val2=a*v[vect[stack[k]]].first+b-v[vect[stack[k]]].second;
    return ((val1>0 && val2<0) || (val1<0 && val2>0));
}

inline double arie(int vect[])
{
    int i;
    double ret=0,temp;
    for (i=2;i<=nrs;++i)
    {
        temp=1LL*(v[vect[stack[i]]].second+v[vect[stack[i-1]]].second)*abs(v[vect[stack[i]]].first-v[vect[stack[i-1]]].first);
        temp/=2;
        if (v[vect[stack[i]]].first>v[vect[stack[i-1]]].first)
            ret-=temp;
        else
            ret+=temp;
    }
    return ret;
}

int main()
{
    freopen("gradina.in","r",stdin);
    freopen("gradina.out","w",stdout);
    scanf("%d",&n);
    for (i=1;i<=n;++i)
    {
        scanf("%d %d",&x,&y);
        v[i]=make_pair(x,y);
        if (v[i].first<xmin)
            xmin=v[i].first;
        if (v[i].second<ymin)
            ymin=v[i].second;
    }
    for (i=1;i<=n;++i)
    {
        if (xmin<0)
            v[i].first-=xmin;
        if (ymin<0)
            v[i].second-=ymin;
    }
    sol=1LL*100000000*100000000;
    for (i=1;i<=n;++i)
        for (j=1;j<=n;++j)
        {
            if (i==j)
                continue;
            a=(double)(v[i].second-v[j].second)/(v[i].first-v[j].first);
            b=v[i].second-a*v[i].first;
            p=q=pct1=pct2=0;
            for (k=1;k<=n;++k)
                if (k!=i && k!=j)
                {
                    if ((v[k].second<a*v[k].first+b && i<j) || (v[k].second>a*v[k].first+b && i>j))
                    {
                        v1[++p]=k;
                        if (!pct1 || (v[k].first<v[v1[pct1]].first || (v[k].first==v[v1[pct1]].first && v[k].second<v[v1[pct1]].second)))
                            pct1=p;
                    }
                    else
                    {
                        v2[++q]=k;
                        if (!pct2 || (v[k].first<v[v2[pct2]].first || (v[k].first==v[v2[pct2]].first && v[k].second<v[v2[pct2]].second)))
                            pct2=q;
                    }
                }
            p+=2;
            v1[p-1]=i;
            v1[p]=j;
            if (!pct1 || (v[v1[p-1]].first<v[v1[pct1]].first || (v[v1[p-1]].first==v[v1[pct1]].first && v[v1[p-1]].second<v[v1[pct1]].second)))
                pct1=p-1;
            if (v[v1[p]].first<v[v1[pct1]].first || (v[v1[p]].first==v[v1[pct1]].first && v[v1[p]].second<v[v1[pct1]].second))
                pct1=p;
            x=v[v1[pct1]].first;
            y=v[v1[pct1]].second;
            sort(v1+1,v1+p+1,cmp());
            exista&=0;
            for (k=1;k<p;++k)
                if ((double)(v[v1[k]].second-y)/(v[v1[k]].first-x)!=
                    (double)(v[v1[k+1]].second-y)/(v[v1[k+1]].first-x))
                        exista.flip(k);
            exista.flip(p);
            stack[nrs=1]=1;
            for (k=2;k<=p;++k)
                if (exista.test(k))
                {
                    while (nrs>=3 && scoate(v1))
                        --nrs;
                    stack[++nrs]=k;
                }
            stack[++nrs]=1;
            s1=arie(v1);
            x=v[v2[pct2]].first;
            y=v[v2[pct2]].second;
            sort(v2+1,v2+q+1,cmp());
            exista&=0;
            for (k=1;k<q;++k)
                if ((double)(v[v2[k]].second-y)/(v[v2[k]].first-x)!=
                    (double)(v[v2[k+1]].second-y)/(v[v2[k+1]].first-x))
                        exista.flip(k);
            exista.flip(q);
            stack[nrs=1]=1;
            for (k=2;k<=q;++k)
                if (exista.test(k))
                {
                    while (nrs>=3 && scoate(v2))
                        --nrs;
                    stack[++nrs]=k;
                }
            stack[++nrs]=1;
            s2=arie(v2);
            if (abs(s1-s2)<sol)
            {
                sol=abs(s1-s2);
                rez&=0;
                for (k=1;k<=n;++k)
                    if (k!=i && k!=j && ((v[k].second<a*v[k].first+b && i<j) || (v[k].second>a*v[k].first+b && i>j)))
                        rez.flip(k);
            }
            else
                if (abs(s1-s2)==sol)
                {
                    nou&=0;
                    for (k=1;k<=n;++k)
                        if (k!=i && k!=j && !((v[k].second<a*v[k].first+b && i<j) || (v[k].second>a*v[k].first+b && i>j)))
                            nou.flip(k);
                    if (nou.test(1))
                        for (k=1;k<=n;++k)
                            nou.flip(k);
                    for (k=1;k<=n;++k)
                        if (nou.test(k)!=rez.test(k))
                        {
                            if (!nou.test(k))
                                rez=nou;
                            break;
                        }
                }
        }
    printf("%.1lf\n",sol);
    for (i=1;i<=n;++i)
        if (!rez.test(i))
            printf("I");
        else
            printf("V");
    return 0;
}