Pagini recente » Cod sursa (job #2419071) | Cod sursa (job #3213625) | Cod sursa (job #2030224) | Cod sursa (job #1742779) | Cod sursa (job #3246052)
#include <fstream>
#include <iomanip>
#include <algorithm>
#include <cmath>
using namespace std;
ifstream in("gradina.in");
ofstream out("gradina.out");
struct punct{
int x, y, tip, ord;
}puncte[255], s1[255], s2[255];
int sol[255];
double minn = 1000000000;
bool cmp(punct a, punct b) {
if (a.x != b.x)
return a.x < b.x;
return a.y < b.y;
}
double arie(punct A, punct B, punct C) {
return A.x * B.y + B.x * C.y + C.x * A.y - B.y * C.x - C.y * A.x - A.y * B.x;
}
double infasuratoare_convexa(punct v[], int n) {
int t[255], st[255];
for (int i = 2; i < n; i++) {
if (arie(v[1], v[n], v[i]) < 0)
t[i] = 1;
else
t[i] = 2;
}
t[1] = t[n] = 0;
int k = 1;
st[1] = 1;
for (int i = 2; i <= n; i++)
if (t[i] == 1 || t[i] == 0) {
while (k > 1 && arie(v[st[k - 1]], v[st[k]], v[i]) < 0)
return -1;
k++;
st[k] = i;
}
int ck = k;
for (int i = n - 1; i >= 1; i--)
if (t[i] == 2 || t[i] == 0) {
while (k > ck && arie(v[st[k - 1]], v[st[k]], v[i]) < 0)
return -1;
k++;
st[k] = i;
}
k--;
double s = 0;
for (int i = 2; i < k; i++)
s += abs(arie(v[1], v[st[i]], v[st[i + 1]])) / 2.0;
return s;
}
void diferenta(int n) {
int cnt1 = 0, cnt2 = 0;
for (int i = 1; i <= n; i++)
if (puncte[i].tip == 1)
s1[++cnt1] = puncte[i];
else
s2[++cnt2] = puncte[i];
if (cnt1 < 3 || cnt2 < 3)
return;
double sum1 = infasuratoare_convexa(s1, cnt1);
double sum2 = infasuratoare_convexa(s2, cnt2);
if (sum1 < 0 || sum2 < 0)
return;
if(abs(sum1 - sum2) == minn) {
int csol[n + 1];
for (int i = 1; i <= n; i++)
csol[i] = sol[i];
for (int i = 1; i <= n; i++) {
if (csol[i] > puncte[i].tip)
break;
if (csol[i] == puncte[i].tip)
continue;
if (csol[i] < puncte[i].tip)
return;
}
for (int i = 1; i <= n; i++)
sol[i] = csol[i];
}
if (abs(sum1 - sum2) < minn) {
minn = abs(sum1 - sum2);
for (int i = 1; i <= n; i++)
sol[puncte[i].ord] = puncte[i].tip;
}
}
int main()
{
int n;
in >> n;
for (int i = 1;i <= n; i++) {
in >> puncte[i].x >>puncte[i].y;
puncte[i].ord = i;
}
sort(puncte + 1, puncte + n + 1, cmp);
for (int i = 1; i < n; i++)
for (int j = i + 1; j <= n; j++) {
for (int k = 1; k <= n; k++)
if (k != i && k != j) {
if (arie(puncte[i], puncte[j], puncte[k]) < 0)
puncte[k].tip = 1;
else
puncte[k].tip = 2;
}
puncte[i].tip = 1;
puncte[j].tip = 2;
diferenta(n);
puncte[i].tip = 2;
puncte[j].tip = 1;
diferenta(n);
}
out << fixed << setprecision(1) << minn << "\n";
for (int i = 1; i <= n; i++)
if (sol[i] == sol[1])
out << 'I';
else
out << 'V';
}