Pagini recente » Cod sursa (job #2458830) | Cod sursa (job #1503434) | Cod sursa (job #1266818) | Cod sursa (job #1951396) | Cod sursa (job #1787792)
#include <cstdio>
#include <algorithm>
#define MAXN 250
long long rez=-1;
int n, sol[2][MAXN+1];
char ans[MAXN], aux[MAXN];
struct myc{
int x, y, z;
bool operator<(const myc u)const{
if(x!=u.x) return x<u.x;
else return y<u.y;
}
}v[MAXN];
inline long long myabs(long long x){
if(x<0) return -x;
else return x;
}
inline long long arie(int i, int j, int p){
return 1LL*v[i].x*v[j].y-1LL*v[j].x*v[i].y+1LL*v[j].x*v[p].y-1LL*v[p].x*v[j].y+1LL*v[p].x*v[i].y-1LL*v[i].x*v[p].y;
}
inline long long convex(int r[]){
int a=0, b=1;
long long ans=0;
for(int i=2; i<r[0]; i++){
if(arie(r[1], r[r[0]], r[i])>0){
if(a==0) a=1, b=i;
else{
if(arie(r[a], r[b], r[i])>0) return 0;
a=b;
b=i;
ans+=arie(r[1], r[b], r[a]);
}
}
}
if((a)&&(arie(r[a], r[b], r[r[0]])>0)) return 0;
a=b;
b=r[0];
if(a!=1) ans+=arie(r[1], r[b], r[a]);
for(int i=r[0]-1; i>1; i--){
if(arie(r[1], r[r[0]], r[i])<0){
if(arie(r[a], r[b], r[i])>0) return 0;
a=b;
b=i;
ans+=arie(r[1], r[b], r[a]);
}
}
if(arie(r[a], r[b], r[1])>0) return 0;
return ans;
}
inline void solutie(){
if(sol[0][0]<3) return ;
if(sol[1][0]<3) return ;
long long arie1=convex(sol[0]);
if(arie1==0) return;
long long arie2=convex(sol[1]);
if(arie2==0) return ;
if((rez==-1)||(myabs(arie1-arie2)<rez)){
rez=myabs(arie1-arie2);
for(int i=1; i<=sol[0][0]; i++) ans[v[sol[0][i]].z]='I';
for(int i=1; i<=sol[1][0]; i++) ans[v[sol[1][i]].z]='V';
if(ans[0]=='V')
for(int i=0; i<n; i++)
if(ans[i]=='I') ans[i]='V';
else ans[i]='I';
}else if(myabs(arie1-arie2)==rez){
for(int i=1; i<=sol[0][0]; i++) aux[v[sol[0][i]].z]='I';
for(int i=1; i<=sol[1][0]; i++) aux[v[sol[1][i]].z]='V';
if(aux[0]=='V')
for(int i=0; i<n; i++)
if(aux[i]=='I') aux[i]='V';
else aux[i]='I';
int p=0;
while((p+1<n)&&(aux[p]==ans[p])) p++;
if(aux[p]<ans[p]){
while(p<n){
ans[p]=aux[p];
p++;
}
}
}
}
int main(){
int l;
FILE *fin, *fout;
fin=fopen("gradina.in", "r");
fout=fopen("gradina.out", "w");
fscanf(fin, "%d", &n);
for(int i=0; i<n; i++){
fscanf(fin, "%d%d", &v[i].x, &v[i].y);
v[i].z=i;
}
std::sort(v, v+n);
for(int i=0; i<n; i++){
for(int j=0; j<i; j++){
sol[0][0]=sol[1][0]=0;
for(int p=0; p<n; p++){
if((p!=i)&&(p!=j)){
l=arie(i, j, p)>0;
sol[l][++sol[l][0]]=p;
}else sol[0][++sol[0][0]]=p;
}
solutie();
sol[0][0]=sol[1][0]=0;
for(int p=0; p<n; p++){
if((p!=i)&&(p!=j)){
l=arie(i, j, p)>0;
sol[l][++sol[l][0]]=p;
}else sol[1][++sol[1][0]]=p;
}
solutie();
}
}
fprintf(fout, "%.1lf\n", rez*0.5);
for(int i=0; i<n; i++)
fputc(ans[i], fout);
fputc('\n', fout);
fclose(fin);
fclose(fout);
return 0;
}