Pagini recente » Cod sursa (job #2637904) | Cod sursa (job #2463116) | Cod sursa (job #27823) | Cod sursa (job #3197778) | Cod sursa (job #1672515)
#include<stdio.h>
#include<string.h>
#include<algorithm>
#include<vector>
#include<deque>
#define lli long long int
#define DIM 252
#define INF 10000000000000000
FILE *f=fopen("gradina.in","r"), *g=fopen("gradina.out","w");
using namespace std;
struct Punct{ int x, y, ind; } v[DIM], ZERO;
vector <int> UNU, DOI;
deque <int> rUNU, rDOI; // reordonat
int N;
lli DIF = INF;
bool SOL[DIM], sol[DIM];
bool cmp( Punct A, Punct B ){
if( A.x < B.x || ( A.x == B.x && A.y < B.y ) )
return 1; return 0;
}
void Citire(){
int i;
fscanf(f,"%d\n",&N);
for(i=1;i<=N;i++){
fscanf(f,"%d %d\n",&v[i].x,&v[i].y);
v[i].ind = i;
} sort(v+1,v+N+1,cmp);
ZERO.x = ZERO.y = 0;
}
lli det( Punct A, Punct B, Punct C ){
return ( A.x * B.y + B.x * C.y + C.x * A.y )
- ( A.y * B.x + B.y * C.x + C.y * A.x );
}
void CreareUNUDOI( int i, int j ){
int k;
UNU.clear(); rUNU.clear();
DOI.clear(); rDOI.clear();
UNU.push_back(i);
DOI.push_back(j);
for(k=1;k<=N;k++)
if( i != k && k != j ){
if( det( v[i], v[j], v[k] ) < 0 )
UNU.push_back(k);
else
DOI.push_back(k);
}
}
void Reordonare( vector <int> OOO, deque <int> &rOOO ){
int i, lp;
lp = OOO.size(); // nr elemente din OOO
rOOO.push_back( OOO[0] );
for(i=1;i<=lp-2;i++){
if( det( v[ OOO[0] ], v[ OOO[lp-1] ], v[ OOO[i] ] ) > 0 )
rOOO.push_back( OOO[i] );
else
rOOO.push_front( OOO[i] );
}
rOOO.push_back( OOO[lp-1] );
rOOO.push_back( rOOO.front() );
rOOO.push_back( rOOO[1] );
}
bool ePolig( deque <int> P ){
int i, lp = P.size(); // nr elemente
for(i=0;i<=lp-3;i++)
if( det( v[ P[i] ], v[ P[i+1] ], v[ P[i+2] ] ) > 0 )
return 0;
return 1;
}
lli Modul( lli OOO ){ if( OOO < 0 ) return -OOO; return OOO; }
lli Aria( deque <int> P ){
lli aria = 0;
int i;
for(i=0;i<=P.size()-2-1;i++)
aria += det( ZERO, v[ P[i] ], v[ P[i+1] ] );
return Modul(aria);
}
void Configuratie(){
int i;
memset(sol,0,sizeof(sol));
for(i=0;i<=rUNU.size()-2;i++)
sol[ v[ rUNU[i] ].ind ] = 1;
if( sol[1] == 1 )
for(i=1;i<=N;i++)
sol[i] = ( sol[i] + 1 ) % 2;
}
bool Comp(){
int i;
for(i=1;i<=N;i++){
if( sol[i] == 0 && SOL[i] == 1 )
return 1;
else if( sol[i] == 1 && SOL[i] == 0 )
return 0;
}
return 0;
}
void Afisare(){
int o;
fprintf(g,"%lld",DIF/2);
if( DIF % 2 == 0 )
fprintf(g,".0\n");
else
fprintf(g,".5\n");
for(o=1;o<=N;o++)
if( SOL[o] == 0 )
fprintf(g,"I");
else
fprintf(g,"V");
fprintf(g,"\n");
}
void Rezolvare(){
int i, j, o;
lli dif;
for(i=1;i<=N;i++)
for(j=1;j<=N;j++)
if( i != j ){
CreareUNUDOI(i,j);
if( UNU.size() >= 3 && DOI.size() >= 3 ){
Reordonare(UNU,rUNU);
Reordonare(DOI,rDOI);
if( ePolig(rUNU) && ePolig(rDOI) ){
dif = Modul( Aria(rUNU) - Aria(rDOI) );
Configuratie();
if( dif < DIF || ( dif == DIF && Comp() ) ){
DIF = dif;
for(o=1;o<=N;o++)
SOL[o] = sol[o];
}
}
}
}
Afisare();
}
int main(){
Citire();
Rezolvare();
return 0;
}