Pagini recente » Cod sursa (job #2024876) | Cod sursa (job #353007) | Cod sursa (job #2029229) | Cod sursa (job #222796) | Cod sursa (job #3247044)
#include <iostream>
#include <fstream>
#include <algorithm>
#include <string>
using namespace std;
struct Punct
{
int indexInitial = -1;
long long x = 0;
long long y = 0;
int parte = -2;
int parteIfasuratoare = -2;
Punct() { }
Punct(long long x, long long y)
{
this->x = x;
this->y = y;
}
};
bool SortareCoordonate(Punct a, Punct b)
{
if (a.x < b.x || (a.x == b.x && a.y < b.y))
return true;
return false;
}
ifstream in("gradina.in");
ofstream out("gradina.out");
int nrPuncte;
Punct* puncte;
int nrElementeStiva;
int* stiva;
long long Arie(Punct a, Punct b, Punct c)
{
return a.x * b.y + b.x * c.y + c.x * a.y - a.y * b.x - b.y * c.x - c.y * a.x;
}
long long InfasuratoareConvexa(int parte)
{
int indexPrimulPunct = -1;
for (int i = 0; i < nrPuncte; i++)
{
if (puncte[i].parte != parte)
continue;
indexPrimulPunct = i;
break;
}
int indexUltimulPunct = -1;
for (int i = nrPuncte - 1; i >= 0; i--)
{
if (puncte[i].parte != parte)
continue;
indexUltimulPunct = i;
break;
}
if (indexUltimulPunct == -1 || indexUltimulPunct == indexPrimulPunct)
return -1;
for (int i = 0; i < nrPuncte; i++)
{
if (puncte[i].parte != parte)
continue;
long long arie = Arie(puncte[indexPrimulPunct], puncte[indexUltimulPunct], puncte[i]);
if (arie < 0)
puncte[i].parteIfasuratoare = -1;
else
puncte[i].parteIfasuratoare = 1;
}
puncte[indexPrimulPunct].parteIfasuratoare = 0;
puncte[indexUltimulPunct].parteIfasuratoare = 0;
bool punctInterior = false;
nrElementeStiva = 0;
for (int i = 0; i < nrPuncte; i++)
{
if (puncte[i].parte != parte || puncte[i].parteIfasuratoare > 0)
continue;
if (nrElementeStiva < 2)
{
stiva[nrElementeStiva] = i;
nrElementeStiva++;
continue;
}
if (nrElementeStiva >= 2 && Arie(puncte[stiva[nrElementeStiva - 2]], puncte[stiva[nrElementeStiva - 1]], puncte[i]) < 0)
{
punctInterior = true;
break;
}
stiva[nrElementeStiva] = i;
nrElementeStiva++;
}
if (punctInterior)
return -1;
nrElementeStiva--;
int offset = nrElementeStiva;
for (int i = nrPuncte - 1; i >= 0; i--)
{
if (puncte[i].parte != parte || puncte[i].parteIfasuratoare < 0)
continue;
if (nrElementeStiva < offset + 2)
{
stiva[nrElementeStiva] = i;
nrElementeStiva++;
continue;
}
if (nrElementeStiva >= offset + 2 && Arie(puncte[stiva[nrElementeStiva - 2]], puncte[stiva[nrElementeStiva - 1]], puncte[i]) < 0)
{
punctInterior = true;
break;
}
stiva[nrElementeStiva] = i;
nrElementeStiva++;
}
if (punctInterior || nrElementeStiva <= 2)
return -1;
nrElementeStiva--;
long long ariePoligon = 0;
for (int i = 1; i < nrElementeStiva - 1; i++)
{
ariePoligon += abs(Arie(puncte[stiva[0]], puncte[stiva[i]], puncte[stiva[i + 1]]));
}
return ariePoligon;
}
int main()
{
in >> nrPuncte;
puncte = new Punct[nrPuncte];
for (int i = 0; i < nrPuncte; i++)
{
puncte[i].indexInitial = i;
in >> puncte[i].x;
in >> puncte[i].y;
}
sort(puncte, puncte + nrPuncte, SortareCoordonate);
long long difAriiMinima = 1000000000000000000;
string configuratieMinima = "";
for (int i = 0; i < nrPuncte; i++)
configuratieMinima += '-';
stiva = new int[nrPuncte];
for (int i = 0; i < nrPuncte; i++)
{
for (int o = 0; o < nrPuncte; o++)
{
for (int j = 0; j < nrPuncte; j++)
{
long long arie = Arie(puncte[i], puncte[o], puncte[j]);
if ((arie < 0 && i < o) || (arie > 0 && i > o))
puncte[j].parte = -1;
else
puncte[j].parte = 1;
}
puncte[i].parte = -1;
puncte[o].parte = 1;
long long ariePoligon1 = InfasuratoareConvexa(-1);
if (ariePoligon1 == -1)
continue;
long long ariePoligon2 = InfasuratoareConvexa(1);
if (ariePoligon2 == -1)
continue;
string configuratie = "";
for (int i = 0; i < nrPuncte; i++)
configuratie += '-';
for (int i = 0; i < nrPuncte; i++)
{
if (puncte[i].parte == -1)
configuratie[puncte[i].indexInitial] = 'V';
else
configuratie[puncte[i].indexInitial] = 'I';
}
if (configuratie[0] == 'V')
{
for (int i = 0; i < nrPuncte; i++)
{
if (puncte[i].parte == -1)
configuratie[puncte[i].indexInitial] = 'I';
else
configuratie[puncte[i].indexInitial] = 'V';
}
}
long long difArii = abs(ariePoligon2 - ariePoligon1);
if (difArii <= difAriiMinima || (difArii == difAriiMinima && configuratie < configuratieMinima))
{
difAriiMinima = difArii;
configuratieMinima = configuratie;
}
}
}
double arieReala = (double)difAriiMinima / 2;
if ((long long)arieReala == arieReala)
out << arieReala << ".0" << '\n';
else
out << arieReala << '\n';
out << configuratieMinima << '\n';
delete[] stiva;
delete[] puncte;
return 0;
}