Pagini recente » Cod sursa (job #2606020) | Cod sursa (job #2948756) | Cod sursa (job #13889) | Cod sursa (job #729827) | Cod sursa (job #3244086)
#include <bits/stdc++.h>
using namespace std;
ifstream f ("gradina.in"); ofstream g ("gradina.out");
struct punct { int x, y; };
punct tarusi_Ion[252], tarusi_Vasile[252], a[252];
int stiva[252];
char sol_curenta[252];
double dif_min;
int n, aux;
int vfIon, vfVasile;
char sol_finala[252];
bool viz[252];
bool cmp (punct a, punct b){
if (a.x > b.x) return false;
if (a.x == b.x && a.y > b.y) return false;
return true;
}
int det (punct a, punct b, punct c){
return (b.x - a.x) * (c.y - a.y) - (b.y - a.y) * (c.x - a.x);
}
double arie_infasuratoare_convexa (punct p[], int m){
double sol = 0;
for (int i = 1; i <= m; i++)
viz[i] = false;
stiva[1] = 1; stiva[2] = 2;
viz[2] = true;
int vf = 2, poz = 2, pas = 1;
while (viz[1] == false){ // pana ajung din nou la primul punct
while (viz[poz] == true){
poz += pas;
if (poz == m) pas = -1;
}
while (vf >= 2 && det(p[stiva[vf - 1]], p[stiva[vf]], p[poz]) < 0){
viz[stiva[vf]] = false;
vf--;
}
vf++;
stiva[vf] = poz;
viz[poz] = true;
}
for (int i = 1; i < vf; i++) sol = sol + det(p[0], p[stiva[i]], p[stiva[i+1]]);
sol = sol / 2;
if (vf != m + 1) aux = 0;
return sol;
}
int main()
{
f >> n;
for (int i = 1; i <= n; i++) f >> a[i].x >> a[i].y;
dif_min = 1000000000;
for (int i = 1; i <= n; i++){
for (int j = i + 1; j <= n; j++){
vfIon = 0;
vfVasile = 0;
for (int k = 1; k <= n; k++){
if (k == i || k == j || det(a[k], a[i], a[j]) < 0){
sol_curenta[k] = 'I';
vfIon++;
tarusi_Ion[vfIon] = a[k];
}
else{
sol_curenta[k] = 'V';
vfVasile++;
tarusi_Vasile[vfVasile] = a[k];
}
}
if (vfIon < 3 || vfVasile < 3) continue;
sort(tarusi_Ion + 1, tarusi_Ion + vfIon + 1, cmp);
sort(tarusi_Vasile + 1, tarusi_Vasile + vfVasile + 1, cmp);
aux = 1;
double dif = abs(arie_infasuratoare_convexa(tarusi_Ion, vfIon) - arie_infasuratoare_convexa(tarusi_Vasile, vfVasile));
if (aux == 0) continue;
if (dif < dif_min){
dif_min = dif;
for (int k = 1; k <= n; k++) sol_finala[k] = sol_curenta[k];
}
}
}
g << setprecision(1) << fixed << dif_min << '\n';
for (int i = 1; i <= n; i++) g << sol_finala[i];
return 0;
}