Pagini recente » Cod sursa (job #1930978) | Cod sursa (job #2404625) | Cod sursa (job #1158207) | Cod sursa (job #453935) | Cod sursa (job #903745)
Cod sursa(job #903745)
#include <iostream>
#include <fstream>
#include <algorithm>
#include <cstring>
using namespace std;
int n, n1, n2;
double sol = 2000000000.0;
char s[256], ssol[256];
struct punct
{
int x, y;
double tg;
};
punct a[256], P1[256], P2[256], st[256];
inline void Read()
{
freopen ("gradina.in", "r", stdin);
scanf ("%d", &n);
int i, x, y;
for (i=1; i<=n; i++)
{
scanf ("%d %d", &x, &y);
a[i].x = x;
a[i].y = y;
if (x==0)
a[i].tg = 2000000000.0;
else
a[i].tg = (y*1.0) / (x*1.0);
}
}
inline long long det(const punct X, const punct Y, const punct Z)
{
// X.x X.y 1
// Y.x Y.y 1
// Z.x Z.y 1
return 1LL*X.x*Y.y + 1LL*X.y*Z.x + 1LL*Y.x*Z.y - 1LL*Y.y*Z.x - 1LL*X.x*Z.y - 1LL*X.y*Y.x;
}
inline bool cmp (const punct A, const punct B)
{
// y1 - y0 / x1 - x0 < y2 - y0 / x2 - x0
// y1 - y0 * x2 - x0 < y2 - y0 * x1 - x0
return A.tg < B.tg;
}
inline double Infasuratoare(punct *v, int nv)
{
int poz, i, vf;
poz = 1;
for (i=2; i<=nv; i++)
{
if (v[i].y < v[poz].y || (v[i].y == v[poz].y && v[i].x < v[poz].x))
poz = i;
}
swap (v[1], v[poz]);
sort(v+2, v+nv+1, cmp);
vf = 0;
st[++vf] = v[1];
st[++vf] = v[2];
for (i=3; i<=nv; i++)
{
while (vf >= 2 && det(st[vf-1], st[vf], v[i]) <= 0)
vf--;
st[++vf] = v[i];
}
if (vf == nv)
{
double aria=0.0, x;
for (i=2; i<nv; i++)
{
x = det(v[1], v[i], v[i+1]);
if (x<0)
x=-x;
aria+=x;
}
return aria;
}
return -1;
}
inline void Solve()
{
int i, j, k, ind;
double a1, a2, dif;
for (i=1; i<=n; i++)
{
for (j=1; j<=n; j++)
{
if (i==j)
continue;
n1 = 0, n2 = 0;
s[i] = 'I';
s[j] = 'V';
n1++;
P1[n1] = a[i];
n2++;
P2[n2] = a[j];
for (k=1; k<=n; k++)
if (i!=k && j!=k)
{
if (det(a[i], a[j], a[k]) < 0)
{
n1++;
P1[n1] = a[k];
s[k] = 'I';
}
else
{
n2++;
P2[n2] = a[k];
s[k] = 'V';
}
}
if (n1 >= 3 && n2 >= 3)
{
a1 = Infasuratoare(P1, n1);
a2 = Infasuratoare(P2, n2);
if (a1 != -1 && a2 != -1)
{
dif = (a1-a2);
if (dif < 0)
dif = -dif;
if (dif < sol)
{
sol = dif;
for (ind = 1; ind <= n; ind++)
ssol[ind] = s[ind];
}
else
if (dif == sol)
{
if (strcmp(s+1, ssol+1) < 0)
for (ind = 1; ind <= n; ind++)
ssol[ind] = s[ind];
}
}
}
}
}
}
inline void Write()
{
FILE*g = fopen("gradina.out", "w");
fprintf (g, "%.1lf\n%s\n", (double)sol/2, ssol+1);
fclose(g);
}
int main()
{
Read();
Solve();
Write();
return 0;
}