Pagini recente » Cod sursa (job #2128650) | Cod sursa (job #2984774) | Cod sursa (job #337601) | Cod sursa (job #984029) | Cod sursa (job #592991)
Cod sursa(job #592991)
#include <cstdio>
#include <cmath>
#include <cstring>
#include <algorithm>
#include <utility>
using namespace std;
#define maxn 255
#define inf (1LL*1000000000*1000000000)
int n, ok, conf[maxn], cand[maxn];
int st[maxn];
long long a1, a2, ns, sol;
pair<int, int> p[maxn];
int xc, yc, v1[maxn], v2[maxn];
double tg[maxn];
inline int cmp(int a, int b)
{
return 1LL*(p[a].second-yc)*(p[b].first-xc)<1LL*(p[b].second-yc)*(p[a].first-xc);
}
long long ab(long long a)
{
if(a>0)
return a;
return -a;
}
int det(int a, int b, int c)
{
long long ar=1LL*p[a].first*p[b].second+1LL*p[b].first*p[c].second+1LL*p[c].first*p[a].second-
(1LL*p[b].first*p[a].second+1LL*p[c].first*p[b].second+1LL*p[a].first*p[c].second);
if(ar==0)
return 0;
if(ar>0)
return 1;
return -1;
}
long long solve(int v[])
{
for(int i=2; i<=v[0]; ++i)
if(p[v[i]]<p[v[1]])
swap(v[1], v[i]);
xc=p[v[1]].first;
yc=p[v[1]].second;
sort(v+2, v+v[0]+1, cmp);
int st0=0;
for(int i=1; i<=v[0]; ++i)
{
st[++st0]=v[i];
while(st0>2 && det(st[st0-2], st[st0-1], st[st0])==-1)
{
--st0;
st[st0]=st[st0+1];
}
}
st[st0+1]=st[1];
long long ar=0;
for(int i=1; i<=st0; ++i)
ar+=1LL*p[st[i]].first*p[st[i+1]].second-1LL*p[st[i+1]].first*p[st[i]].second;
return ab(ar);
}
void verif()
{
if(ns<sol)
{
sol=ns;
memset(conf, 0, sizeof(conf));
for(int k=1; k<=v2[0]; ++k)
conf[v2[k]]=1;
}
else
if(ns==sol)
{
memset(cand, 0, sizeof(cand));
for(int k=1; k<=v2[0]; ++k)
cand[v2[k]]=1;
ok=0;
for(int k=1; k<=n; ++k)
{
if(cand[k]<conf[k])
{
ok=1;
break;
}
if(cand[k]>conf[k])
break;
}
if(ok)
for(int k=1; k<=n; ++k)
conf[k]=cand[k];
memset(cand, 0, sizeof(cand));
for(int k=1; k<=v1[0]; ++k)
cand[v1[k]]=1;
ok=0;
for(int k=1; k<=n; ++k)
{
if(cand[k]<conf[k])
{
ok=1;
break;
}
if(cand[k]>conf[k])
break;
}
if(ok)
for(int k=1; k<=n; ++k)
conf[k]=cand[k];
}
}
int main()
{
freopen("gradina.in", "r", stdin);
freopen("gradina.out", "w", stdout);
scanf("%d", &n);
for(int i=1; i<=n; ++i)
scanf("%d%d", &p[i].first, &p[i].second);
sol=inf;
for(int i=1; i<=n; ++i)
for(int j=i+1; j<=n; ++j)
{
v1[0]=v2[0]=0;
for(int k=1; k<=n; ++k)
{
if(i==k || j==k)
continue;
if(det(i, j, k)<0)
v1[++v1[0]]=k;
else
v2[++v2[0]]=k;
}
v1[++v1[0]]=j;
v2[++v2[0]]=i;
if(v1[0]<3 || v2[0]<3)
continue;
a1=solve(v1);
a2=solve(v2);
ns=ab(a1-a2);
verif();
v1[0]=v2[0]=0;
for(int k=1; k<=n; ++k)
{
if(i==k || j==k)
continue;
if(det(i, j, k)<0)
v1[++v1[0]]=k;
else
v2[++v2[0]]=k;
}
v1[++v1[0]]=i;
v2[++v2[0]]=j;
if(v1[0]<3 || v2[0]<3)
continue;
a1=solve(v1);
a2=solve(v2);
ns=ab(a1-a2);
verif();
}
if(sol%2)
printf("%lld.5\n", sol/2);
else
printf("%lld.0\n", sol/2);
for(int i=1; i<=n; ++i)
if(conf[i])
printf("V");
else
printf("I");
printf("\n");
return 0;
}