Cod sursa(job #535381)

Utilizator hadesgamesTache Alexandru hadesgames Data 17 februarie 2011 10:00:50
Problema Gradina Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.93 kb
#include <cstdio>
#include <algorithm>
using namespace std;
#define fi first
#define se second
#define mp make_pair
typedef pair<int,int> point;
FILE *in,*out;
int n;
int c[400],b[400];
pair<point,int> p[400];
point a[400];
int stiva[400],v[400];
char x[400],rez[400];
inline double Abs(double x)
{
	return x<0?-x:x;
}
void gen_sir(char x[])
{
	char c1='I',c2='V';
	int i,ind;
	if (c[1]==1)
	{
		c1='V';
		c2='I';
	}
	ind=1;
	for (i=1;i<=n;i++)
		if (ind<=b[0] && b[ind]==i)
		{
			x[p[i].se]=c1;
			ind++;
		}
		else
			x[p[i].se]=c2;
}

bool comp(char a[],char b[])
{
	int i;
	for (i=1;i<=n;i++)
	{
		if (a[i]<b[i])
			return 1;
		if (a[i]>b[i])
			return 0;
	}
	return 0;
}
struct ecuatie
{
	long long C,A,B;
};
ecuatie gen_ecuatie(point p1,point p2)
{
	ecuatie rez;
	rez.A=p1.se-p2.se;
	rez.B=p2.fi-p1.fi;
	rez.C=((long long)p1.fi)*p2.se-((long long)p2.fi)*p1.se;
	return rez;
}
long long semn(point p , const ecuatie & ec)
{
	return ec.A*p.fi+ec.B*p.se+ec.C;
}
/*x y 1
x1 y1 1
x2 y2 1

= x*y1 + x1*y2 + y * x2 - x2*y1 - y*x1 -x*y2
= x(y1-y2) + y(x2-x1) + x1*y2 -x2*y1;*/
double convex_hull_arie (int b[])
{
	int i=1,pas=1,u=2;
	memset(v,0,sizeof(v));
	stiva[1]=1;
	stiva[2]=2;
	v[2]=1;
	for (i=3;i>=1;i+=pas)
	{
		if (i==b[0]+1)
		{
			pas*=-1;
			i-=2;
		}
		if (v[i])
			continue;
		while (u>1 && semn(a[b[i]],gen_ecuatie(a[b[stiva[u-1]]],a[b[stiva[u]]]))>0)
		{
			v[stiva[u]]=0;
			u--;
		}
		u++;
		stiva[u]=i;
		v[i]=1;
	}
	long long arie=0;
	for (i=1;i<u;i++)
	{
		arie+=((long long)a[b[stiva[i]]].fi)*a[b[stiva[i+1]]].se-((long long)a[b[stiva[i+1]]].fi)*a[b[stiva[i]]].se;
	}
	return Abs(arie)/2.0;
	
	
}
double arie(int x,int y,ecuatie &ec)
{
	int i;
	double aux1,aux2;
	b[0]=c[0]=0;
	for (i=1;i<=n;i++)
	{
		if (x==i)
		{
			b[0]++;
			b[b[0]]=i;
			continue;
		}
		if (y==i)
		{
			c[0]++;
			c[c[0]]=i;
			continue;
		}
		if (semn(a[i],ec)<0)
		{
			b[0]++;
			b[b[0]]=i;
		}
		else
		{
			c[0]++;
			c[c[0]]=i;
		}
	}
	if (c[0]<3||b[0]<3)
		return 1<<30;
	aux1=convex_hull_arie(b);
	aux2=convex_hull_arie(c);
	return Abs(aux1-aux2);
}
int main()
{
	int i,j,k;
	double minv=1<<29,r1;
	ecuatie ec;
	in=fopen("gradina.in","r");
	out=fopen("gradina.out","w");
	fscanf(in,"%d",&n);
	for (i=1;i<=n;i++)
	{
		fscanf(in,"%d%d",&p[i].fi.fi,&p[i].fi.se);
		p[i].se=i;
	}
	sort(p+1,p+n+1);
	for (i=1;i<=n;i++)
		a[i]=p[i].fi;
	for (i=1;i<=n;i++)
		for (j=1;j<=n;j++)
			if(i!=j)
			{
				if (i<j)
					ec=gen_ecuatie(a[i],a[j]);
				else
					ec=gen_ecuatie(a[j],a[i]);
				r1=arie(i,j,ec);
				if (r1<minv)
				{
					gen_sir(x);
					minv=r1;
					for (k=1;k<=n;k++)
						rez[k]=x[k];
				}
				else
				{
					
					if (r1==minv)
					{
						gen_sir(x);
						if (comp(x,rez))
						{
							for (k=1;k<=n;k++)
								rez[k]=x[k];
						}
					}
				}
			}
	fprintf(out,"%lf\n%s\n",minv,rez+1);
}