Pagini recente » Cod sursa (job #700877) | Cod sursa (job #2928904) | Cod sursa (job #2475822) | Cod sursa (job #2532138) | Cod sursa (job #3270485)
#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;
using ll = long long;
const ll oo = 1e9;
ifstream fin("gradina.in");
ofstream fout("gradina.out");
struct punct{
ll x, y, idx;
bool operator == (punct b){
return (b.x == x && b.y == y);
}
};
ll 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){
if(v.size() < 3) return 0;
for(ll i = 2; i < v.size(); i++){
if(det( v[i - 2], v[i - 1], v[i] ) < 0) return 0;
}
return 1;
}
void gas_start(vector< punct > & v){
start.x = start.y = oo;
for(int i = 0; i < v.size(); i++){
if( v[i].x < start.x || (start.x == v[i].x && v[i].y < start.y) ) start = v[i];
}
}
signed main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
ll n; in >> n;
punct v[n];
ll mini = LLONG_MAX;
string sol;
for(int i = 0; i < n; i++) sol.push_back('V');
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(ll i = 0; i < n; i++){
for(ll j = 0; j < n; j++){
if(i == j) continue;
vector< punct > st, dr;
for(ll k = 0; k < n; k++){
if(k == i) st.push_back(v[k]);
else if(k == j) dr.push_back(v[k]);
else if( det(v[i], v[j], v[k]) > 0 ) st.push_back(v[k]);
else dr.push_back(v[k]);
}
if(st.size() < 3 || dr.size() < 3) continue;
gas_start(st);
sort(st.begin(), st.end(), cmp);
gas_start(dr);
sort(dr.begin(), dr.end(), cmp);
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(ll k = 0; k < st.size(); k++) cout << "( " << st[k].x << " , " << st[k].y << " ) ";
// cout << '\n';
// cout << " -- > dr : ";
// for(ll k = 0; k < dr.size(); k++) cout << "( " << dr[k].x << " , " << dr[k].y << " ) ";
// cout << '\n';
ll A1 = 0, A2 = 0;
for(ll 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(ll 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);
// 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(ll k = 0; k < st.size(); k++) s[ st[k].idx ] = 'I';
for(ll k = 0; k < dr.size(); k++) s[ dr[k].idx ] = 'V';
sol = min(sol, s);
}
}
}
out << fixed << setprecision(1) << (db)mini / (db)2 << '\n';
out << sol << '\n';
return 0;
}