Pagini recente » Cod sursa (job #2427053) | Cod sursa (job #1148023) | Cod sursa (job #2538492) | Cod sursa (job #2814750) | Cod sursa (job #3270257)
#include <iostream>
#include <fstream>
#include <vector>
#include <map>
#include <stack>
#include <climits>
#include <iomanip>
#include <algorithm>
//#include <bits/stdc++.h>
#define in fin
#define out fout
using namespace std;
using db = double;
ifstream fin("gradina.in");
ofstream fout("gradina.out");
struct punct{
db x, y, idx;
bool operator == (punct b){
return (b.x == x && b.y == y);
}
};
db det(punct a, punct b, punct c){
return ( a.x * b.y + b.x * c.y + c.x * a.y - c.x * b.y - a.x * c.y - b.x * a.y );
}
punct start;
bool cmp(punct a, punct b){
if(a == start) return true;
if(b == start) return false;
return (det( start, a, b ) > 0);
}
bool e_convex(vector< punct > & v){
for(int i = 2; i < v.size(); i++){
if(det( v[i - 2], v[i - 1], v[i] ) < 0) return 0;
}
return 1;
}
signed main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int n; in >> n;
punct v[n];
db mini = 50000001;
string sol;
for(int i = 0; i < n; i++) sol.push_back('V');
start.x = start.y = 0;
for(int i = 0; i < n; i++){
in >> v[i].x >> v[i].y;
v[i].idx = i;
}
sort(v + 0, v + n, cmp);
for(int i = 0; i < n; i++){
for(int j = 0; j < n; j++){
if(i == j) continue;
vector< punct > st, dr;
for(int k = 0; k < n; k++){
if( det(v[i], v[j], v[k]) > 0 ) st.push_back(v[k]);
else dr.push_back(v[k]);
}
bool convex_1 = e_convex(st), convex_2 = e_convex(dr);
if(!convex_1 || !convex_2) continue;
// cout << "Stabilim I ( " << v[i].x << " , " << v[i].y << " ) si J ( " << v[j].x << " , " << v[j].y << " )\n";
// cout << " -- > st : ";
// for(int k = 0; k < st.size(); k++) cout << "( " << st[k].x << " , " << st[k].y << " ) ";
// cout << '\n';
// cout << " -- > dr : ";
// for(int k = 0; k < dr.size(); k++) cout << "( " << dr[k].x << " , " << dr[k].y << " ) ";
// cout << '\n';
db A1 = 0, A2 = 0;
for(int k = 0; k + 1 < st.size(); k++){
A1 += st[k].x * st[k + 1].y - st[k + 1].x * st[k].y;
}
A1 += st.back().x * st[0].y - st[0].x * st.back().y;
for(int k = 0; k + 1 < dr.size(); k++){
A2 += dr[k].x * dr[k + 1].y - dr[k + 1].x * dr[k].y;
}
A2 += dr.back().x * dr[0].y - dr[0].x * dr.back().y;
A1 /= 2; A2 /= 2;
// cout << " -- > A1 = " << A1 << " A2 = " << A2 << '\n';
if(abs(A1 - A2) < mini) mini = abs(A1 - A2);
if(mini == abs(A1 - A2)){
string s;
s.resize(n);
for(int k = 0; k < st.size(); k++) s[ st[k].idx ] = 'I';
for(int k = 0; k < dr.size(); k++) s[ dr[k].idx ] = 'V';
if(s[0] == 'V'){
for(int k = 0; k < n; k++){
if(s[i] == 'I') s[i] = 'V';
else s[i] = 'I';
}
}
sol = min(sol, s);
}
}
}
out << fixed << setprecision(6) << mini << '\n';
out << sol << '\n';
return 0;
}