Cod sursa(job #289008)

Utilizator irene_mFMI Irina Iancu irene_m Data 26 martie 2009 12:01:30
Problema Gradina Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.73 kb
#include <fstream.h>
#include <math.h>
#include <values.h>
#include <iomanip.h>
#include <stdio.h>
typedef int vect[255];
int n,x[255],j,y[255],sol[255],solf[255],xi[255],yi[255],xv[255],yv[255],p[255],i,xx,yy,x2,y2,a,b,c,nri,nrv,k,t,nri2,nrv2,l;
double s1,s2,s3,mins=1000000;

void cit()
{
	int i,aux;
	j=1;
	ifstream fin("gradina.in");
	fin>>n;
	for(i=1;i<=n;i++)
	{
		fin>>x[i]>>y[i];
		if(y[i]<y[j] || (y[i]==y[j] && x[i]<x[j]))
			j=i;
		p[i]=i;
	}
	aux=x[1]; x[1]=x[j]; x[j]=aux;
	aux=y[1]; y[1]=y[j]; y[j]=aux;
	aux=p[1]; p[1]=p[j]; p[j]=aux;
	fin.close();
}

void swap(int i, int j)
{
	int aux=x[i];
	x[i]=x[j];
	x[j]=aux;
	aux=y[i];
	y[i]=y[j];
	y[j]=aux;
	aux=p[i];
	p[i]=p[j];
	p[j]=aux;
}

double prod_vec(vect x,vect y,int i,int j,int k)
{
	return (x[j]-x[i])*(y[k]-y[i])-(x[k]-x[i])*(y[j]-y[i]);
}

void sort(int beg, int end)
{
	if(end>beg+1)
	{
		//punct piv=arr[beg];
		int l=beg+1, r=end;
		while(l<r)
		{
			if(prod_vec(x,y,j,l,beg)>0)
				  l++;
			else
			{
				r--;
				swap(l,r);
			}
		}
		l--;
		swap(l,beg);
		sort(beg, l);
		sort(r, end);
	}
}

void infas(vect x,vect y,int n,int &m)
{
	vect s;
	int i;
	s[1]=1;
	s[2]=2;
	m=2;
	for(i=3;i<=n;i++)
	{
		while(m>=2 && prod_vec(x,y,s[m],i,s[m-1])<=0)
			m--;
		m++;
		s[m]=i;
	}
	s[n]=0;
}

double triunghi(int x1,int y1,int x2,int y2,int x3,int y3)
{
	double p=0.5;
	long det;
	det=x1*y2+x2*y3+x3*y1-x3*y2-x2*y1-x1*y3;
	det=abs(det);
	p*=det;
	return p;
}	

double arie(vect x,vect y,int n)
{
	double s=0;
	int i;
	for(i=2;i<n;i++)
		s+=triunghi(x[1],y[1],x[i],y[i],x[i+1],y[i+1]);
	return s;
}
	
int main()
{
	cit();
	sort(2,n+1);
	for(i=1;i<n;i++)
	{
		xx=x[i]; yy=y[i];
		for(j=1;j<=n;j++)
			if(i!=j)
		{
			x2=x[j]; y2=y[j];
			a=y2-yy;
			b=xx-x2;
			c=x2*yy-xx*y2; nri=1; nrv=1;
			xi[1]=xx; yi[1]=yy; xv[1]=x2; yv[1]=y2;
			nri2=0; nrv2=0;
			sol[p[i]]=1; sol[p[j]]=2;
			for(k=1;k<=n;k++)
				if(k!=i && k!=j)
				{
					t=a*x[k]+b*y[k]+c;
					if(t>0)
					{
						nri++;
						xi[nri]=x[k];
						yi[nri]=y[k];
						sol[p[k]]=1;
					}
					else
					{
						nrv++;
						xv[nrv]=x[k];
						yv[nrv]=y[k];
						sol[p[k]]=2;
					}
				}
			infas(xi,yi,nri,nri2);
			infas(xv,yv,nrv,nrv2);
			if(nri2==nri && nrv2==nrv)
			{
				s1=arie(xi,yi,nri);
				s2=arie(xv,yv,nrv);
				if(s1>s2)
					s3=s1-s2;
				else
					s3=s2-s1;
				if(s3<mins)
				{
					mins=s3;
					for(l=1;l<=n;l++)
						solf[l]=sol[l];
				}
			}
		}		
	}			
	ofstream fout("gradina.out");
	fout.precision(1);
	fout<<setiosflags(ios::showpoint)<<mins;
	fout<<'\n';
	for(i=1;i<=n;i++)
		if(solf[i]==2)
			fout<<'I';
		else
			fout<<'V';
	fout.close();
	return 0;
}