Pagini recente » Cod sursa (job #2559187) | Cod sursa (job #665567) | Cod sursa (job #54017) | Cod sursa (job #1881017) | Cod sursa (job #2603621)
#include <bits/stdc++.h>
using namespace std;
ifstream in("gradina.in");
ofstream out("gradina.out");
int n,s[251];
char t[251];
double mini=1000000000000;
struct pct
{ int x,y,id;
}a[251];
vector <pct> v[2];
bool cmp(pct a,pct b)
{ if(a.y==b.y)
return a.x<b.x;
return a.y<b.y;
}
bool stanga(pct a,pct b,pct c)
{ return (a.x-b.x)*(c.y-b.y)<(a.y-b.y)*(c.x-b.x);
}
void solve(int ok,pct a,pct b,pct c,int k)
{ if(v[ok].size()<k)
{ v[ok].push_back(c);
return;
}
while(v[ok].size()>=k && !stanga(v[ok][v[ok].size()-2],v[ok][v[ok].size()-1],c))
v[ok].pop_back();
v[ok].push_back(c);
}
double aria(pct a,pct b,pct c)
{ return abs((a.x-c.x)*(b.y-c.y)-(a.y-c.y)*(b.x-c.x))/2.0;
}
int main()
{ in>>n;
for(int i=1;i<=n;i++)
in>>a[i].x>>a[i].y,a[i].id=i;
sort(a+1,a+n+1,cmp);
for(int x=1;x<=n;x++)
{ for(int y=1;y<=n;y++)
{ if(x==y)
continue;
for(int i=1;i<=n;i++)
{ if(((a[x].x-a[y].x)*(a[i].y-a[y].y)>=(a[x].y-a[y].y)*(a[i].x-a[y].x) && i!=y) || i==x)
solve(0,a[x],a[y],a[i],2),s[a[i].id]=0;
else
solve(1,a[x],a[y],a[i],2),s[a[i].id]=1;
}
int k0=v[0].size()+1,k1=v[1].size()+1;
for(int i=n-1;i>=1;i--)
{ if(((a[x].x-a[y].x)*(a[i].y-a[y].y)>=(a[x].y-a[y].y)*(a[i].x-a[y].x) && i!=y) || i==x)
solve(0,a[x],a[y],a[i],k0),s[a[i].id]=0;
else
solve(1,a[x],a[y],a[i],k1),s[a[i].id]=1;
}
if(v[0].size()<4 || v[1].size()<4)
{ v[0].clear();
v[1].clear();
continue;
}
v[0].pop_back();
v[1].pop_back();
k0=v[0].size();
k1=v[1].size();
double r0=0;
for(int i=1;i<k0-1;i++)
r0+=aria(v[0][i],v[0][i+1],v[0][0]);
double r1=0;
for(int i=1;i<k1-1;i++)
r1+=aria(v[1][i],v[1][i+1],v[1][0]);
if(mini>abs(r1-r0))
{ mini=abs(r1-r0);
for(int i=1;i<=n;i++)
if(s[i]==s[1])
t[i]='I';
else
t[i]='V';
}
v[0].clear();
v[1].clear();
}
}
out<<setprecision(1)<<fixed<<mini<<'\n';
for(int i=1;i<=n;i++)
out<<t[i];
in.close();
out.close();
return 0;
}