Cod sursa(job #1666503)
Utilizator | Data | 28 martie 2016 03:31:06 | |
---|---|---|---|
Problema | Gradina | Scor | 0 |
Compilator | cpp | Status | done |
Runda | Arhiva de probleme | Marime | 5.96 kb |
#include<cstdio>
#include<algorithm>
#include<cmath>
#define INF 1000000000000000LL
using namespace std;
struct pct{
int x;
int y;
int p;
}v[300],x[300],y[300],z[300],aa,bb,cc;
int n,i,j,k,a,b,c,nx,ny,nr,ok,p,u,w[300],q[300],sol[300];
long long vmin,l,r,s;
FILE *f,*g;
int cmp(pct a,pct b){
if( a.x != b.x )
return a.x < b.x;
return a.y < b.y;
}
long long det(pct a,pct b,pct c){
return 1LL * ( b.x - a.x ) * ( c.y - a.y ) - 1LL * ( c.x - a.x ) * ( b.y - a.y );
}
long long modul(long long a){
if(a<0)
return -a;
return a;
}
long long pg(pct x[],int m){
aa = x[1];
bb = x[m];
p = 0;
u = m + 1;
for(int i=1;i<=m;i++){
if( i < m && x[i].y == x[ i + 1 ].y && det( aa, bb, x[i] ) * det( aa, bb, x[ i + 1 ] ) > 0 ){
return INF;
}
if( det( aa, x[i], bb ) >= 0 )
z[ ++p ] = x[i];
else
z[ --u ] = x[i];
}
z[ m + 1 ] = z[1];
z[ m + 2 ] = z[2];
for(int i=1;i<=m;i++){
if( det( z[i], z[ i + 1 ], z[ i + 2 ] ) < 0 )
return INF;
}
long long s = 0;
for(int i=1;i<=m-1;i++){
s += det( cc , z[ i ], z[ i + 1 ] ) ;
}
return modul(s);
}
int main(){
f=fopen("gradina.in","r");
g=fopen("gradina.out","w");
fscanf(f,"%d",&n);
for(i=1;i<=n;i++){
fscanf(f,"%d%d",&v[i].x,&v[i].y);
v[i].p = i;
}
cc.x = cc.y = 0;
sort(v+1,v+n+1,cmp);
vmin = INF;
for(i=1;i<=n;i++){
for(j=i+1;j<=n;j++){
if( i != j ){
nx = ny = 0;
aa = v[i];
bb = v[j];
for(k=1;k<=300;k++){
x[k].x = x[k].y = x[k].p = y[k].x = y[k].y = y[k].p = 0;
}
for(k=1;k<=n;k++) {
if ( k == i ){
x[ ++nx ] = v[k];
q[ v[k].p ] = 1;
}
else if ( k == j ){
y[ ++ny ] = v[k];
q[ v[k].p ] = 2;
}
else if( det( v[k], aa, bb) < 0 ){
x[ ++nx ] = v[k];
q[ v[k].p ] = 1;
}
else{
y[ ++ny ] = v[k];
q[ v[k].p ] = 2;
}
}
if( nx >= 3 && ny >= 3 ){
l = pg(x,nx);
r = pg(y,ny);
if( l != INF && r != INF ){
if( modul( l - r ) < vmin ){
vmin = modul( l - r );
for(k=1;k<=n;k++){
sol[k] = q[k];
}
}
else if( modul( l - r ) == vmin ){
ok = 0;
for(k=1;k<=n;k++){
if( q[k] < sol[k] ){
ok = 1;
break;
}
if( sol[k] < q[k] ){
ok = 0;
break;
}
}
if( ok ){
for(k=1;k<=n;k++){
sol[k] = q[k];
}
}
}
}
}
nx = ny = 0;
for(k=1;k<=300;k++){
x[k].x = x[k].y = x[k].p = y[k].x = y[k].y = y[k].p = 0;
}
for(k=1;k<=n;k++) {
if ( k == j ){
x[ ++nx ] = v[k];
q[ v[k].p ] = 1;
}
else if ( k == i ){
y[ ++ny ] = v[k];
q[ v[k].p ] = 2;
}
else if( det( v[k], aa, bb) < 0 ){
x[ ++nx ] = v[k];
q[ v[k].p ] = 1;
}
else{
y[ ++ny ] = v[k];
q[ v[k].p ] = 2;
}
}
if( nx >= 3 && ny >= 3 ){
l = pg(x,nx);
r = pg(y,ny);
if( l != INF && r != INF ){
if( modul( l - r ) < vmin ){
vmin = modul( l - r );
for(k=1;k<=n;k++){
sol[k] = q[k];
}
}
else if( modul( l - r ) == vmin ){
ok = 0;
for(k=1;k<=n;k++){
if( q[k] < sol[k] ){
ok = 1;
break;
}
if( sol[k] < q[k] ){
ok = 0;
break;
}
}
if( ok ){
for(k=1;k<=n;k++){
sol[k] = q[k];
}
}
}
}
}
}
}
}
fprintf(g,"%lld",vmin/2);
if( vmin % 2 )
fprintf(g,".5\n");
else
fprintf(g,".0\n");
for(i=1;i<=n;i++){
if( sol[i] == 1 )
fprintf(g,"I");
else
fprintf(g,"V");
}
fclose(f);
fclose(g);
return 0;
}