Pagini recente » Cod sursa (job #2322368) | Cod sursa (job #1234202) | Cod sursa (job #1801171) | Cod sursa (job #2340193) | Cod sursa (job #94180)
Cod sursa(job #94180)
#include <cstdio>
#include <vector>
#include <algorithm>
#include <cmath>
using namespace std;
#define NMAX 255
#define x first
#define y second
vector<pair<int,int> > P;
int N, H[NMAX], inH[NMAX], X[NMAX], Y[NMAX], Sol[NMAX], I[NMAX];
long double Dmin, BIG;
void read()
{
int i, a, b;
freopen("gradina.in", "r", stdin);
scanf("%d", &N);
for (i = 0; i < N; i++)
{
scanf("%d%d", &a, &b);
P.push_back(make_pair(a,b));
I[i] = i;
}
for (a = 0; a < N; a++)
for (b = a+1; b < N; b++)
if ((P[a].x>P[b].x)||((P[b].x==P[a].x)&&(P[a].y>P[b].y)))
{
i = P[a].x; P[a].x = P[b].x; P[b].x = i;
i = P[a].y; P[a].y = P[b].y; P[b].y = i;
i = I[a]; I[a] = I[b]; I[b] = i;
}
}
int cross(int a, int b, int c)
{
int x1 = P[a].x, x2 = P[b].x, x3 = P[c].x;
int y1 = P[a].y, y2 = P[b].y, y3 = P[c].y;
return (x1*y2-x2*y1+x2*y3-x3*y2+x3*y1-x1*y3);
}
long double hull()
{
int i, nH = 0, n1 = 0;
long double arie=0;
for (i = 0; i < N && nH<2; i++)
if (X[i]) n1++, H[nH++] = i, inH[i] = 1;
for (; i < N; i++)
if (X[i])
{
while ((nH>1)&&(cross(H[nH-2], H[nH-1], i)<=0)) inH[ H[--nH] ] = 0;
H[nH++] = i; inH[i] = 1;
n1++;
}
if (n1<3) return BIG;
for (i = N-1; i >= 0; i--)
if (X[i]&&!inH[i])
{
while ((nH>1)&&(cross(H[nH-2], H[nH-1], i)<=0)) inH[ H[--nH] ] = 0;
H[nH++] = i; inH[i] = 1;
}
if ((nH<2)&&(cross(H[nH-2], H[nH-1], i)<=0)) inH[ H[--nH] ] = 0;
H[nH] = H[0];
if (nH<n1) return BIG;
for (i = 0; i < nH; i++)
arie += (long double)(P[ H[i] ].x*P[ H[i+1] ].y-P[ H[i+1] ].x*P[ H[i] ].y);
return 0.5*fabs(arie);
}
void solve()
{
int i, j, k;
long double s1, s2, dpart;
long double a=50000000;
BIG=a*a; Dmin = BIG;
for (i = 0; i < N; i++)
for (j = i+1; j < N; j++)
{
for (k = 0; k < N; k++)
{
X[k] = 0;
if (cross(i,j,k)<0) X[k] = 1;
}
X[i] = 1;
s1 = hull();
if (s1==BIG) s2 = 0;
else {
for (k = 0; k < N; k++) X[k] ^= 1, Y[k] = X[k];
s2 = hull(); }
dpart = fabs(s1-s2);
if (s2==BIG) dpart = BIG;
for (k = 0; k < N; k++)
{
X[k] = 0;
if (cross(i,j,k)<0) X[k] = 1;
}
X[j] = 1;
s1 = hull();
if (s1==BIG) s2 = 0;
else {
for (k = 0; k < N; k++) X[k] ^= 1;
s2 = hull(); }
if (s2==BIG) s1 = 2*BIG;
if (fabs(s1-s2)<dpart)
{
if (fabs(s1-s2)<Dmin)
{
Dmin = fabs(s1-s2);
for (k = 0; k < N; k++) Sol[I[k]] = X[k];
}
else
if (fabs(s1-s2)==Dmin)
{
for (k = 0; k < N && Sol[I[k]]==X[k];k++);
if (X[k]<Sol[k])
for (; k < N; k++) Sol[I[k]] = X[k];
}
}
if (dpart<Dmin)
{
Dmin = dpart;
for (k = 0; k < N; k++) Sol[I[k]] = Y[k];
}
else
if (dpart==Dmin)
{
for (k = 0; k < N && Sol[I[k]]==Y[k];k++);
if (Y[k]<Sol[k])
for (; k < N; k++) Sol[I[k]] = Y[k];
}
}
}
void write()
{
freopen("gradina.out", "w", stdout);
printf("%Lf\n", Dmin);
for (int i = 0; i < N; i++)
if (Sol[i]) printf("V"); else printf("I");
printf("\n");
}
int main()
{
read();
solve();
write();
return 0;
}