Pagini recente » Cod sursa (job #2567811) | Cod sursa (job #545242) | Cod sursa (job #2737926) | Cod sursa (job #425646) | Cod sursa (job #2339479)
#include <bits/stdc++.h>
#define int long long
using namespace std;
ifstream fi("gradina.in");
ofstream fo("gradina.out");
const int NMAX = 300;
struct punct
{
int x, y;
};
struct punctS
{
punct M;
int poz;
};
bool operator <(const punct &a, const punct &b)
{
if (a.x != b.x)
return a.x < b.x;
return a.y < b.y;
}
bool operator <(const punctS &a, const punctS &b)
{
return a.M < b.M;
}
punctS P[NMAX];
punct sus[NMAX], jos[NMAX];
int cntSus, cntJos;
int n;
punct stivaSus[NMAX], stivaJos[NMAX];
int kSus, kJos;
bool afara;
int verifica(punct A, punct B, punct C)
{
return A.x * (B.y - C.y) + B.x * (C.y - A.y) + C.x * (A.y - B.y);
}
long double faTot(punct A[NMAX], int n) // returneaza aria
{
if (n == 2)
return 0;
kJos = 0;
kSus = 0;
stivaSus[++kSus] = A[1];
stivaJos[++kJos] = A[1];
for (int i = 2; i <= n; i++)
{
if (verifica(A[1], A[n], A[i]) > 0 || i == n) // sus
{
while (kSus >= 2 && verifica(stivaSus[kSus - 1], stivaSus[kSus], A[i]) > 0)
kSus--, afara = 1;
stivaSus[++kSus] = A[i];
}
if (verifica(A[1], A[n], A[i]) < 0 || i == n) // jos
{
while (kJos >= 2 && verifica(stivaJos[kJos - 1], stivaJos[kJos], A[i]) < 0)
kJos--, afara = 1;
stivaJos[++kJos] = A[i];
}
}
vector <punct> poligon;
for (int i = 1; i <= kSus; i++)
poligon.push_back(stivaSus[i]);
for (int i = kJos - 1; i >= 1; i--)
poligon.push_back(stivaJos[i]);
long double ret = 0;
int l = poligon.size();
for (int i = 1; i < l; i++)
{
ret += (poligon[i - 1].x * poligon[i].y - poligon[i].x * poligon[i - 1].y);
}
ret = ret / 2.00;
return abs(ret);
}
signed main()
{
fi >> n;
for (int i = 1; i <= n; i++)
{
fi >> P[i].M.x >> P[i].M.y, P[i].poz = i;
P[i].M.x += 50000000;
P[i].M.y += 50000000;
}
sort(P + 1, P + n + 1);
long double minim = 2000000000;
string configOptim = "";
for (int i = 1; i <= n; i++)
{
for (int j = 1; j <= n; j++)
{
if (i == j)
continue;
// i la ion, j la domnu vasile
punct baza, varf; // baza=punctul care e mai in stanga
if (P[j] < P[i])
baza = P[j].M, varf = P[i].M;
else
baza = P[i].M, varf = P[j].M;
cntSus = cntJos = 0;
// sus punem J, jos punem I
string config = "";
config.resize(n);
for (int k = 1; k <= n; k++)
{
if ((verifica(baza, varf, P[k].M) > 0 && k != i) || k == j) // e sus, la Vasile
{
sus[++cntSus] = P[k].M;
config[P[k].poz - 1] = 'V';
}
else
{
jos[++cntJos] = P[k].M;
config[P[k].poz - 1] = 'I';
}
}
afara = 0;
long double a1 = faTot(sus, cntSus);
if (afara)
continue;
afara = 0;
long double a2 = faTot(jos, cntJos);
if (afara)
continue;
string opus = "";
for (auto pp: config)
opus += (pp == 'I' ? 'V' : 'I');
if (abs(a2 - a1) < minim || (abs(a2 - a1) == minim && (config < configOptim || opus < configOptim)))
{
minim = abs(a2 - a1);
configOptim = min(config, opus);
}
}
}
fo << fixed << setprecision(1) << minim << "\n" << configOptim;
return 0;
}