Cod sursa(job #483130)

Utilizator cosmyoPaunel Cosmin cosmyo Data 6 septembrie 2010 23:03:55
Problema Gradina Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 4.1 kb
#include<fstream>
#include<vector>
#include<cstdlib>
#define x first
#define y second
#define NMAX 300
#define inf 10000000.0
using namespace std;
typedef pair<long,long> pt;
vector< pt > p(NMAX),a(NMAX);
vector<long> st,uz(NMAX),m(NMAX);
pt w;

long n;
double Min=inf;
void cit()
{ifstream fin("gradina.in");
	fin>>n;
	for(long i=1;i<=n;++i)
		fin>>a[i].x>>a[i].y;
 fin.close();
}
long ec(pt p,pt q,pt w)
{long f,a,b,c;
 a=p.y-q.y;
 b=q.x-p.x;
 c=-q.x*p.y+q.y*p.x;
 f=a*w.x+b*w.y+c;
 return f>0;
}
int cmp(pt a,pt b)
{return (a.y-w.y)*(b.x-w.x)<(a.x-w.x)*(b.y-w.y);
}
long double arie(pt a,pt b,pt c)
{return ((b.x-c.x)*(b.y-a.y)+(a.x-b.x)*(b.y-c.y));}
void hull(long n)
{long i,o;
 o=1;
  for(i=2;i<=n;++i)
	  if((p[i].x<p[o].x)||(p[i].x==p[o].x&&p[i].y<p[o].y))
		  o=i;
 w=p[o];
 p.erase(p.begin()+o);
 --n;
 p[0]=w;
 sort(p.begin()+1,p.begin()+n+1,cmp);
 st.push_back(0);
 st.push_back(1);
  for(i=2;i<=n;++i)
  { while(st.size()>1&&arie(p[st[st.size()-2]],p[st[st.size()-1]],p[i])<=0)
	  st.pop_back();
   st.push_back(i);
  }
}
long double aria(long n)
{long i;
 long double s=0;
 if(n<=1)
	 return 0;
 else
 for(i=1;i<=n-1;++i)
 	s+=fabsl(arie(p[st[0]],p[st[i]],p[st[i+1]]))/2;
return s;
}
void afis()
{long i,j,k,nr;
 double si,sv,d;
 ofstream fout("gradina.out");
  for(i=1;i<=n;++i)
	  for(j=i+1;j<=n;++j)
	  {nr=0; 
	   for(k=1;k<=n;++k)
		   uz[k]=0;
	    for(k=1;k<=n;++k)
			if(k!=i&&k!=j&&ec(a[i],a[j],a[k]))
				{p[++nr]=a[k];
			     uz[k]=1;
				}
		p[++nr]=a[i];p[++nr]=a[j];uz[i]=1;uz[j]=1;		
		st.clear();
			if(nr>=3)
			 hull(nr);
		si=aria(st.size()-1);
		nr=0;
			for(k=1;k<=n;++k)
				if(k!=i&&k!=j&&!ec(a[i],a[j],a[k]))
					{p[++nr]=a[k];
					 uz[k]=2;
					}
		st.clear();
			if(nr>=3)
			 hull(nr);
		sv=aria(st.size()-1);
		d=sv-si;
		if(fabsl(d)<Min)
		{Min=fabsl(d);
		 for(k=1;k<=n;++k)
			 m[k]=uz[k];
		}
		if(fabsl(d)==Min)
		{Min=fabsl(d);
		 if(uz<m)
			 for(k=1;k<=n;++k)
				 m[k]=uz[k];
		}
	  nr=0; 
	    for(k=1;k<=n;++k)
			if(k!=i&&k!=j&&ec(a[i],a[j],a[k]))
				{p[++nr]=a[k];
			     uz[k]=1;
				}
		p[++nr]=a[i];uz[i]=1;		
		st.clear();
			if(nr>=3)
			 hull(nr);
		si=aria(st.size()-1);
		nr=0;
			for(k=1;k<=n;++k)
				if(k!=i&&k!=j&&!ec(a[i],a[j],a[k]))
					{p[++nr]=a[k];
					 uz[k]=2;
					}
		st.clear();
		p[++nr]=a[j];uz[j]=2;
			if(nr>=3)
			 hull(nr);
		sv=aria(st.size()-1);
		d=sv-si;
		if(fabsl(d)<Min)
		{Min=fabsl(d);
		 for(k=1;k<=n;++k)
			 m[k]=uz[k];
		}
		if(fabsl(d)==Min)
		{Min=fabsl(d);
		 if(uz<m)
			 for(k=1;k<=n;++k)
				 m[k]=uz[k];
		}
	  nr=0; 
	    for(k=1;k<=n;++k)
			if(k!=i&&k!=j&&ec(a[i],a[j],a[k]))
				{p[++nr]=a[k];
			     uz[k]=1;
				}
		p[++nr]=a[j];uz[j]=1;		
		st.clear();
			if(nr>=3)
			 hull(nr);
		si=aria(st.size()-1);
		nr=0;
			for(k=1;k<=n;++k)
				if(k!=i&&k!=j&&!ec(a[i],a[j],a[k]))
					{p[++nr]=a[k];
					 uz[k]=2;
					}
		st.clear();
		p[++nr]=a[i];uz[i]=2;
			if(nr>=3)
			 hull(nr);
		sv=aria(st.size()-1);
		d=sv-si;
		if(fabsl(d)<Min)
		{Min=fabsl(d);
		 for(k=1;k<=n;++k)
			 m[k]=uz[k];
		}
		if(fabsl(d)==Min)
		{Min=fabsl(d);
		 if(uz<m)
			 for(k=1;k<=n;++k)
				 m[k]=uz[k];
		} 
	  nr=0; 
	    for(k=1;k<=n;++k)
			if(k!=i&&k!=j&&ec(a[i],a[j],a[k]))
				{p[++nr]=a[k];
			     uz[k]=1;
				}
		st.clear();
			if(nr>=3)
			 hull(nr);
		si=aria(st.size()-1);
		nr=0;
			for(k=1;k<=n;++k)
				if(k!=i&&k!=j&&!ec(a[i],a[j],a[k]))
					{p[++nr]=a[k];
					 uz[k]=2;
					}
		st.clear();
		p[++nr]=a[j];uz[j]=2;p[++nr]=a[i];uz[i]=2;
			if(nr>=3)
			 hull(nr);
		sv=aria(st.size()-1);
		d=sv-si;
		if(fabsl(d)<Min)
		{Min=fabsl(d);
		 for(k=1;k<=n;++k)
			 m[k]=uz[k];
		}
		if(fabsl(d)==Min)
		{Min=fabsl(d);
		 if(uz<m)
			 for(k=1;k<=n;++k)
				 m[k]=uz[k];
		} 
	  }
  fout.precision(16); 	  
  fout<<Min<<'\n';
   if(m[1]==2)
	   for(i=1;i<=n;++i)
		   if(m[i]==1)
			   m[i]=2;
		   else
			   m[i]=1;
   for(i=1;i<=n;++i)
	   if(m[i]==1)
	   fout<<'I'<<" ";
	   else
		   fout<<'V'<<' ';
 fout.close();
}
int main()
{cit();
 afis();
 return 0;
}