Pagini recente » Cod sursa (job #1617917) | Cod sursa (job #1015328) | Cod sursa (job #1852514) | Cod sursa (job #1759150) | Cod sursa (job #486831)
Cod sursa(job #486831)
#include<fstream>
#include<algorithm>
#include<string>
using namespace std;
const char iname[]="gradina.in";
const char oname[]="gradina.out";
const int maxn=256;
ifstream f(iname);
ofstream g(oname);
struct point
{
int x,y,z;
bool operator<(const point& v) const
{
if(x!=v.x)
return x<v.x;
return y<v.y;
}
} a[maxn],b[maxn],c[maxn];
int n,i,j,k,p,q,x,y,mint,stiva[maxn],used[maxn];
string aux,rez;
int arry(point a,point b,point c)
{
return a.x*(b.y-c.y)+b.x*(c.y-a.y)+c.x*(a.y-b.y);
}
int chull(point a[],int n)
{
if(n<3)
return 0;
stiva[0]=1;
stiva[1]=2;
memset(used,0,sizeof(used));
int i=2,k=1,stp=1;
used[2]=1;
while(used[1]==0)
{
if(i==n)
stp=-1;
while(used[i]==1)
i+=stp;
while(k&&arry(a[stiva[k-1]],a[stiva[k]],a[i])>0)
used[stiva[k--]]=0;
used[stiva[++k]=i]=1;
}
int area=0;
if(k!=n)
return 0;
for(i=1;i<=k;++i)
area+=a[stiva[i-1]].x*a[stiva[i]].y-a[stiva[i]].x*a[stiva[i-1]].y;
return max(area,-area);
}
int main()
{
f>>n;
for(i=1;i<=n;++i)
f>>a[i].x>>a[i].y,a[i].z=i;
sort(a+1,a+n+1);
mint=(1<<31)-1;
aux.resize(n);
for(i=1;i<=n;++i)
for(j=1;j<=n;++j)
if(i!=j)
{
p=q=0;
for(k=1;k<=n;++k)
if(k-i&&k-j)
if(arry(a[i],a[j],a[k])>0)
b[++p]=a[k];
else
c[++q]=a[k];
else
if(k==i)
b[++p]=a[k];
else
c[++q]=a[k];
x=chull(b,p);
y=chull(c,q);
if(x&&y)
if(max(x-y,y-x)<=mint)
{
for(k=1;k<=p;++k)
aux[b[k].z-1]='I';
for(k=1;k<=q;++k)
aux[c[k].z-1]='V';
if(max(x-y,y-x)==mint)
rez=min(rez,aux);
else
rez=aux;
mint=max(x-y,y-x);
}
}
g.setf(ios::fixed,ios::floatfield);
g.precision(1);
g<<(double)mint/2.0<<"\n";
g<<rez<<"\n";
}