Pagini recente » Cod sursa (job #592244) | Cod sursa (job #450859) | Cod sursa (job #1898054) | Cod sursa (job #784161) | Cod sursa (job #212903)
Cod sursa(job #212903)
#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;
}