Pagini recente » Rating moraru laura (liciu) | Cod sursa (job #2216630) | Cod sursa (job #2458123) | Cod sursa (job #1141930) | Cod sursa (job #2965612)
#include <fstream>
#include <stack>
#include <algorithm>
#include <iomanip>
using namespace std;
ifstream f("gradina.in");
ofstream g("gradina.out");
const long long CCW = -1, COL = 0, CW = 1;
#define MAX 50000000LL
long long n, i, j, k, nr1, nr2, aux, mindif = 4000000000000000000LL, whohas[252], ok;
long long area1, area2;
long long lowerHull[252], upperHull[252], lowerN, upperN;
char solconfig[252], newconfig[252];
struct Punct
{
long long x, y, i;
}
tarusi[252], tarusi1[252], tarusi2[252];
struct Dreapta
{
long long a, b, c;
}
limdr;
bool operator < (const Punct &a, const Punct &b)
{
if (a.x < b.x)
return true;
else if (a.x == b.x) {
if (a.y < b.y)
return true;
}
return false;
}
Dreapta createLine(const Punct &p1, const Punct &p2)
{
Dreapta aux;
aux.a = p1.y - p2.y;
aux.b = p2.x - p1.x;
aux.c = -(aux.a * p1.x + aux.b * p1.y);
return aux;
}
long long getOrientation(const Punct &a, const Punct &b, const Punct &c)
{
long long crossProduct = (b.x - a.x) * (c.y - b.y) - (b.y - a.y) * (c.x - b.x);
if (crossProduct == 0)
return COL;
if (crossProduct > 0)
return CCW;
return CW;
}
inline long long getTrapezoidArea(const Punct &a, const Punct &b)
{
return (b.x - a.x) * (a.y + b.y + 2*MAX);
}
long long getConvexHullArea(Punct *pcts, long long n)
{
long long i = 0;
lowerHull[++lowerN] = 1;
lowerHull[++lowerN] = 2;
for (i = 3; i <= n; i++) {
while (lowerN >= 2 && getOrientation(pcts[lowerHull[lowerN-1]], pcts[lowerHull[lowerN]], pcts[i]) == CW)
lowerN--;
lowerHull[++lowerN] = i;
}
upperHull[++upperN] = n;
upperHull[++upperN] = n-1;
for (i = n-2; i >= 1; i--) {
while (upperN >= 2 && getOrientation(pcts[upperHull[upperN-1]], pcts[upperHull[upperN]], pcts[i]) == CW)
upperN--;
upperHull[++upperN] = i;
}
lowerN--;
upperN--;
if (lowerN + upperN == n) {
for (i = 1; i <= upperN; i++)
lowerHull[lowerN+i] = upperHull[i];
lowerHull[lowerN+upperN+1] = lowerHull[1];
upperN = 0;
lowerN = 0;
long long area = 0.0;
for (long long i = 1; i <= n; i++) {
area = area + getTrapezoidArea(pcts[lowerHull[i]], pcts[lowerHull[i+1]]);
}
return area;
}
return 0;
}
int main()
{
f >> n;
for (i = 1; i <= n; i++) {
f >> tarusi[i].x >> tarusi[i].y;
tarusi[i].i = i;
}
sort(tarusi+1, tarusi+n+1);
for (i = 1; i <= n; i++) {
for (j = 1; j <= n; j++) {
if (i == j)
continue;
nr1 = 0;
nr2 = 0;
for (k = 1; k <= n; k++) {
aux = getOrientation(tarusi[i], tarusi[j], tarusi[k]);
if (aux == COL || aux == CCW) {
tarusi1[++nr1] = tarusi[k];
whohas[tarusi[k].i] = 0;
}
else {
tarusi2[++nr2] = tarusi[k];
whohas[tarusi[k].i] = 1;
}
}
if (nr1 >= 3 && nr2 >= 3) {
area1 = abs(getConvexHullArea(tarusi1, nr1));
area2 = abs(getConvexHullArea(tarusi2, nr2));
if (!area1 || !area2)
continue;
if (whohas[1] == 0) {
for (k = 1; k <= n; k++)
newconfig[k] = (whohas[k] == 0) ? 'I' : 'V';
}
else {
for (k = 1; k <= n; k++)
newconfig[k] = (whohas[k] == 0) ? 'V' : 'I';
}
if (abs(area1-area2) < mindif) {
mindif = abs(area1-area2);
for (k = 1; k <= n; k++)
solconfig[k] = newconfig[k];
}
else if (abs(area1-area2) == mindif) {
ok = 0;
for (k = 1; k <= n; k++) {
if (newconfig[k] < solconfig[k]) {
ok = 1;
k = n+1;
}
else if (newconfig[k] > solconfig[k]) {
k = n+1;
}
}
if (ok == 1) {
for (k = 1; k <= n; k++)
solconfig[k] = newconfig[k];
}
}
}
}
}
g << std::fixed << setprecision(1);
g << ((long double)mindif) / 2.0;
g << '\n';
g << (solconfig+1);
f.close();
g.close();
return 0;
}