Mai intai trebuie sa te autentifici.

Cod sursa(job #535434)

Utilizator hadesgamesTache Alexandru hadesgames Data 17 februarie 2011 11:02:52
Problema Gradina Scor 30
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.13 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];
char x[400],rez[400],v[400];
inline long long Abs(long long x)
{
	return x<0?-x:x;
}
void gen_sir(char x[])
{
	char c1='I',c2='V';
	int i,ind;
	if (p[c[1]].se==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)//safe
{
	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)//safe
{
	return ec.A*((long long)p.fi)+ec.B*((long long)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;*/
long long convex_hull_arie (int b[])//safe
{
	int i=1,pas=1,u=2;
/*	for (i=1;i<=b[0];i++)
		v[i]=0;*/
	stiva[1]=b[1];
	stiva[2]=b[2];
	v[b[2]]=1;;
	for (i=3;i>=1;i+=pas)
	{
		if (i==b[0]+1)
		{
			pas*=-1;
			i-=2;
		}
		if (v[b[i]])
			continue;
		while (u>1 && semn(a[b[i]],gen_ecuatie(a[stiva[u-1]],a[stiva[u]]))>0)
		{
			v[stiva[u]]=0;
			--u;
		}
		++u;
		stiva[u]=b[i];
		v[b[i]]=1;
	}
	long long arie=0;
	for (i=1;i<u;++i)
	{
		arie+=((long long)a[stiva[i]].fi)*((long long)a[stiva[i+1]].se)-((long long)a[stiva[i+1]].fi)*((long long) a[stiva[i]].se);
	}
	return Abs(arie);
	
	
}
long long arie(int x,int y,ecuatie &ec)//safe
{
	int i;
	long long 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 ((long long )1)<<55;
	memset(v,0,n+10);
	aux1=convex_hull_arie(b);
	aux2=convex_hull_arie(c);
	return Abs(aux1-aux2);
}
int main()
{
	int i,j,k;
	long long minv=((long long)1)<<55,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||(i==1&&j==2))
				{
					gen_sir(x);
					minv=r1;
					memcpy(rez,x,n+1);
				}
				else
				{
					
					if (r1==minv)
					{
						gen_sir(x);
						if (comp(x,rez))
						{
							memcpy(rez,x,n+1);
						}
					}
				}
			}
	fprintf(out,"%.1lf\n%s\n",minv/2 + (minv%2)/2.0,rez+1);
	fclose(in);
	fclose(out);
	return 0;
}