Pagini recente » Cod sursa (job #1875089) | Cod sursa (job #1190677) | Cod sursa (job #840412) | Cod sursa (job #424575) | Cod sursa (job #212942)
Cod sursa(job #212942)
#include <stdio.h>
#include <algorithm>
using namespace std;
#define maxl 300
#define infi 2147000000
int n,i,j,a,b,c,k,ind,nr;
int x[maxl],y[maxl],sol[maxl][2];
int init[maxl][2];
int p[maxl][2],v[maxl],inf[maxl];
double tg[maxl],s1,s2,ch,minim=infi,sup;
void ind_det() {
int x1,y1,x2,y2;
if (x[i] < x[j]) {
x1 = x[i]; y1 = y[i];
x2 = x[j]; y2 = y[j];
}
else if (x[i] > x[j]) {
x1 = x[j];y1 = y[j];
x2 = x[i];y2 = y[i];
}
else if (y[i] < y[j]) {
x1 = x[i]; y1 = y[i];
x2 = x[j]; y2 = y[j];
}
else {
x1 = x[j]; y1 = y[j];
x2 = x[i]; y2 = y[i];
}
a = y1 - y2;
b = x2 - x1;
c = x1 * y2 - x2 * y1;
}
inline int cmp(int x, int y) {
if (tg[x] < tg[y]) return true;
if (tg[x] > tg[y]) return false;
if (tg[x] == tg[y]) {
if (p[x][0] > p[y][0]) return true;
else return false;
}
}
double sup_inf() {
int i;
tg[1] = -infi; v[1] = 1;
for (i = 2; i <= ind; i++) {
if (p[i][0] - p[1][0] != 0) tg[i] = (double)(p[i][1] - p[1][1]) / (p[i][0] - p[1][0]);
else tg[i] = infi;
v[i] = i;
}
sort(v + 1,v + ind + 1,cmp);
inf[1] = v[1]; inf[2] = v[2]; k = 2;
for (i = 3; i <= ind; i++) {
while (k > 1 && (p[inf[k]][0] - p[inf[k-1]][0]) * (p[v[i]][1] - p[inf[k-1]][1]) -
(p[v[i]][0] - p[inf[k-1]][0]) * (p[inf[k]][1] - p[inf[k-1]][1]) < 0) {
k--;
}
inf[++k] = v[i];
while (k > 2 && ((p[inf[1]][0] - p[inf[k]][0]) * (p[inf[2]][1] - p[inf[k]][1]) -
(p[inf[2]][0] - p[inf[k]][0]) * (p[inf[1]][1] - p[inf[k]][1])) < 0) {
k--;
}
}
if (k != ind) return -1;
else {
sup = p[inf[ind]][0] * p[inf[1]][1] - p[inf[1]][0] * p[inf[ind]][1];
for (i = 1; i < ind; i++)
sup += p[inf[i]][0] * p[inf[i+1]][1] - p[inf[i+1]][0] * p[inf[i]][1];
sup = (double)sup / 2;
return sup;
}
}
int main() {
freopen("gradina.in","r",stdin);
freopen("gradina.out","w",stdout);
scanf("%d",&n);
for (i = 1; i <= n; i++) {
scanf("%d %d",&x[i],&y[i]);
init[i][0] = x[i];
init[i][1] = y[i];
}
for (i = 1; i <= n-1; i++)
for (j = i + 1; j <= n; j++) {
if (x[i] > x[j]) {
a = x[i]; x[i] = x[j]; x[j] = a;
a = y[i]; y[i] = y[j]; y[j] = a;
}
if (x[i] == x[j] && y[i] > y[j]) {
a = y[i]; y[i] = y[j]; y[j] = a;
}
}
for (i = 1; i <= n; i++)
for (j = 1; j <= n; j++)
if (i != j) {
ind_det();
ind = 1; p[ind][0] = x[i]; p[ind][1] = y[i];
for (k = 1; k <= n; k++)
if (k != i && k != j && a * x[k] + b * y[k] + c < 0) {
p[++ind][0] = x[k];p[ind][1] = y[k];
}
s1 = sup_inf();
ind = 1; p[ind][0] = x[j];p[ind][1] = y[j];
for (k = 1; k <= n; k++)
if (k != i && k != j && a * x[k] + b * y[k] + c > 0) {
p[++ind][0] = x[k]; p[ind][1] = y[k];
}
s2 = sup_inf();
if (s1 < s2) {
ch = s1; s1 = s2; s2 = ch;
}
if (s1 - s2 < minim && s1 != -1 && s2 != -1) {
minim = s1 - s2; nr = ind;
for (k = 1; k <= ind; k++) {
sol[k][0] = p[k][0];
sol[k][1] = p[k][1];
}
}
}
printf("%.1lf\n",minim);
for (i = 1; i <= n; i++) {
a=0;
for (j = 1; j <= nr; j++)
if (init[i][0] == sol[j][0] && init[i][1] == sol[j][1]) {
a = 1;
break;
}
if (!a) printf("I");
else printf("V");
}
printf("\n");
return 0;
}