Pagini recente » Cod sursa (job #2468813) | Cod sursa (job #2845485) | Cod sursa (job #87256) | Cod sursa (job #2259011) | Cod sursa (job #3248274)
#include <iostream>
#include <fstream>
#include <algorithm>
#include <iomanip>
using namespace std;
ifstream fin("gradina.in");
ofstream fout("gradina.out");
const int MAX_SIZE = 120000;
int minim = 1e9;
int stk[MAX_SIZE + 1];
int sol[MAX_SIZE + 1];
struct date {
double x, y;
int parte;
int ord;
//int tip
} puncte[MAX_SIZE + 1], s1[MAX_SIZE + 1], s2[MAX_SIZE + 1];
bool comp(date a, date b) {
if (a.x != b.x) {
return a.x < b.x;
}
return a.y < b.y;
}
double arie(date a, date b, date 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(date v[], int n) {
for (int i = 2; i < n; ++i) {
if (arie(v[1], v[n], v[i]) < 0) {
v[i].parte = 1;
} else {
v[i].parte = 2;
}
}
int k = 1;
stk[1] = 1;
for (int i = 2; i <= n; ++i) {
if (v[i].parte == 1 || v[i].parte == 0) {
while (k > 1 && arie(v[stk[k - 1]], v[stk[k]], v[i]) < 0) {
--k;
}
++k;
stk[k] = i;
}
}
int copy_k = k;
stk[k] = n;
for (int i = n - 1; i >= 1; --i) {
if (v[i].parte == 2 || v[i].parte == 0) {
while (k > copy_k && arie(v[stk[k - 1]], v[stk[k]], v[i]) < 0) {
--k;
}
++k;
stk[k] = i;
}
}
--k; //invata de ce
double suma = 0;
for (int i = 2; i < k; ++i) {
suma += abs(arie(v[1], v[i], v[i + 1])) / 2.0;
}
return suma;
}
void diferenta(int n) {
int cnt1 = 0;
int cnt2 = 0;
for (int i = 1; i <= n; i++) {
if (puncte[i].parte == 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) == minim) {
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].parte) { //in loc de tip pun parte
break;
}
if (csol[i] == puncte[i].parte) {
continue;
}
if (csol[i] < puncte[i].parte) {
return;
}
}
for (int i = 1; i <= n; ++i) {
sol[i] = csol[i];
}
}
if (abs(sum1 - sum2) < minim) {
minim = abs(sum1 - sum2);
for (int i = 1; i <= n; ++i) {
sol[puncte[i].ord] = puncte[i].parte;
}
}
}
int main() {
int n;
fin >> n;
for (int i = 1; i <= n; ++i) {
fin >> puncte[i].x >> puncte[i].y;
puncte[i].ord = i; //vezi de ce
}
sort(puncte + 1, puncte + n + 1, comp);
for (int i = 1; i < n; ++i) {
for (int j = 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].parte = 1; //inainte puncte[k].tip
} else {
puncte[k].parte = 2;
}
}
puncte[i].parte = 1;
puncte[j].parte = 2;
diferenta(n);
puncte[i].parte = 2;
puncte[j].parte = 1;
diferenta(n);
}
}
}
fout << minim;
for (int i = 1; i <= n; ++i) {
if (sol[i] == sol[1]) {
fout << 'I';
} else {
fout << 'V';
}
}
return 0;
}