Cod sursa(job #476171)

Utilizator ionutz32Ilie Ionut ionutz32 Data 10 august 2010 00:20:23
Problema Gradina Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 6.97 kb
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <bitset>
#include <vector>

using namespace std;

int n,i,xmin,ymin,j,k,stack[255],nrs,io,x,y,poz[255],p,q;
double a,b,s1,s2,sol;
bitset<255> rez,nou,mult;
pair<int,int> v[255],init[255];
bool ok;
vector<int> v1,v2;

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

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

struct cmp
{
    inline bool operator()(const pair<int,int> &a,const pair<int,int> &b)const
    {
        return a.first<b.first || (a.first==b.first && a.second<b.second);
    }
};

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

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

inline double arie(vector<int> vect)
{
    int i;
    double ret=0,temp;
    for (i=2;i<=nrs;++i)
    {
        temp=1LL*(v[vect[stack[i]-1]].second+v[vect[stack[i-1]-1]].second)*abs(v[vect[stack[i]-1]].first-v[vect[stack[i-1]-1]].first);
        temp/=2;
        if (v[vect[stack[i]-1]].first>v[vect[stack[i-1]-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;
        init[i]=v[i];
    }
    sort(v+1,v+n+1,cmp());
    for (i=1;i<=n;++i)
        for (j=1;j<=n;++j)
            if (init[i]==v[j])
            {
                poz[i]=j;
                break;
            }
    sol=1LL*100000000*100000000;
    for (i=1;i<=n;++i)
        for (j=1;j<=n;++j)
        {
            if (i==j)
                continue;
			ok=true;
            v1.clear();
			v2.clear();
			mult&=0;
            if (v[i].first!=v[j].first)
            {
                a=(double)(v[i].second-v[j].second)/(v[i].first-v[j].first);
                b=v[i].second-a*v[i].first;
                for (k=1;k<=n;++k)
                    if ((v[k].second<a*v[k].first+b && i<j) || (v[k].second>a*v[k].first+b && i>j) || egal(v[k].second,a*v[k].first+b))
                        v1.push_back(k);
                    else
					{
						v2.push_back(k);
						mult.flip(k);
					}
            }
            else
                for (k=1;k<=n;++k)
                    if ((v[k].first<v[i].first && i<j) || (v[k].first>v[i].first) && i>j || (v[k].first==v[i].first))
                        v1.push_back(k);
                    else
					{
                        v2.push_back(k);
						mult.flip(k);
					}
			p=v1.size();
			q=v2.size();
			if (p<=2 || q<=2)
				continue;
            stack[nrs=1]=1;
			nou&=0;
			nou.flip(1);
            for (k=2;k<=p;++k)
            {
                while (stack[nrs]>1 && scoate(v1))
                    nou.flip(stack[nrs--]);
                stack[++nrs]=k;
				nou.flip(k);
            }
            for (k=p-1;k>=1;--k)
            {
                while (stack[nrs]<p && scoate2(v1,p))
					if (!nou.test(stack[nrs--]))
					{
						ok=false;
						break;
					}
                stack[++nrs]=k;
            }
			if (!ok)
				continue;
            if (p!=nrs-1)
                continue;
            s1=arie(v1);
            stack[nrs=1]=1;
			nou&=0;
			nou.flip(1);
            for (k=2;k<=q;++k)
            {
                while (stack[nrs]>1 && scoate(v2))
                    nou.flip(stack[nrs--]);
                stack[++nrs]=k;
				nou.flip(k);
            }
            for (k=q-1;k>=1;--k)
			{
                while (stack[nrs]<q && scoate2(v2,q))
					if (!nou.test(stack[nrs--]))
                    {
						ok=false;
						break;
					}
				stack[++nrs]=k;
			}
			if (!ok)
				continue;
            if (q!=nrs-1)
                continue;
            s2=arie(v2);
            if (abs(s1-s2)<sol)
            {
                sol=abs(s1-s2);
                rez&=0;
                for (k=1;k<=n;++k)
                    if (poz[k]!=i && poz[k]!=j && mult.test(poz[k]))
                        rez.flip(k);
                if (rez.test(1))
                    for (k=1;k<=n;++k)
                        rez.flip(k);
            }
            else
                if (abs(s1-s2)==sol)
                {
                    nou&=0;
                    for (k=1;k<=n;++k)
                        if (poz[k]!=i && poz[k]!=j && mult.test(poz[k]))
                            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;
}