Pagini recente » Cod sursa (job #567619) | Cod sursa (job #1740873) | Cod sursa (job #67345)
Cod sursa(job #67345)
Utilizator |
Mircea Pasoi domino |
Data |
24 iunie 2007 13:20:49 |
Problema |
Gradina |
Scor |
Ascuns |
Compilator |
cpp |
Status |
done |
Runda |
|
Marime |
2.6 kb |
#include <stdio.h>
#include <algorithm>
#include <string>
using namespace std;
#define MAX_N 405
#define FIN "gradina.in"
#define FOUT "gradina.out"
#define x first.first
#define y first.second
#define idx second
#define mp make_pair
#define abs(x) ((x) < 0 ? -(x) : (x))
typedef pair<pair<int, int>, int> point;
int N, n1, n2, L[MAX_N], R[MAX_N], nl, nr;
point P[MAX_N], P1[MAX_N], P2[MAX_N];
char inL[MAX_N], inR[MAX_N];
pair<double, string> Res;
int sgn(point a, point b, point c)
{
long long t = (long long) (b.x-a.x)*(c.y-a.y) - (long long) (c.x-a.x)*(b.y-a.y);
return t < 0 ? -1 : t > 0 ? +1 : 0;
}
double convex_hull(point P[], int N)
{
int i, n;
double area = 0.0;
if (N < 3) return -1.0;
L[0] = R[0] = 0; nl = 2;
L[1] = R[1] = 1; nr = 2;
inL[0] = inL[1] = inR[0] = inR[1] = 1;
for (i = 2; i < N; i++)
{
for (; nl > 1 && sgn(P[L[nl-2]], P[L[nl-1]], P[i]) < 0; nl--)
{
inL[n = L[nl-1]] = 0;
if (!inR[n]) return -1.0;
}
for (; nr > 1 && sgn(P[R[nr-2]], P[R[nr-1]], P[i]) > 0; nr--)
{
inR[n = R[nr-1]] = 0;
if (!inL[n]) return -1.0;
}
inL[L[nl++] = i] = inR[R[nr++] = i] = 1;
}
if (nl+nr != N+2) return -1.0;
for (i = nr-2; i >= 0; i--) L[nl++] = i;
for (i = 0; i+1 < nl; i++)
area += (double) P[L[i]].x*P[L[i+1]].y - (double) P[L[i+1]].x*P[L[i]].y;
return abs(area);
}
int main(void)
{
int i, j, k;
double a1, a2;
string s;
freopen(FIN, "r", stdin);
freopen(FOUT, "w", stdout);
scanf("%d", &N);
for (i = 0; i < N; i++)
{
scanf("%d %d", &P[i].x, &P[i].y);
P[i].idx = i;
}
sort(P, P+N);
Res = mp(1e13, "");
for (i = 0; i < N; i++)
for (j = 0; j < N; j++)
{
if (i == j) continue;
s.resize(N);
P1[0] = P[i]; P2[0] = P[j]; n1 = n2 = 1;
s[P[i].idx] = 'I'; s[P[j].idx] = 'V';
for (k = 0; k < N; k++)
{
if (k == i || k == j) continue;
if (sgn(P[min(i, j)], P[max(i, j)], P[k]) < 0)
P1[n1++] = P[k], s[P[k].idx] = 'I';
else
P2[n2++] = P[k], s[P[k].idx] = 'V';
}
if ((a1 = convex_hull(P1, n1)) < 0.0) continue;
if ((a2 = convex_hull(P2, n2)) < 0.0) continue;
Res = min(Res, mp(abs(a1-a2), s));
}
printf("%.1f\n%s\n", Res.first*0.5, Res.second.c_str());
return 0;
}