Pagini recente » Cod sursa (job #1944625) | Cod sursa (job #2204082) | Cod sursa (job #414412) | Cod sursa (job #2680529) | Cod sursa (job #1250327)
#include <cstdio>
#include <vector>
#include <algorithm>
#include <string>
#include <cmath>
#include <fstream>
#include <iomanip>
#include <cstring>
#define x first
#define y second
#define NMAX 257
#define LL long long
using namespace std;
string Ans;
pair < int, int > a[NMAX];
vector < int > Sol1, Sol2, Sol3, Sol4;
char s[2][NMAX];
int Ind[NMAX];
LL Min = (1 << 30);
int Viz[NMAX];
inline bool Cmp(int Ind1, int Ind2){
if(a[Ind1].x == a[Ind2].x)
return a[Ind1].y < a[Ind2].y;
return a[Ind1].x < a[Ind2].x;;
}
inline LL cp(pair < int, int> A, pair < int, int > B , pair < int, int > C){
return 1LL * (B.x - A.x) * (C.y - A.y) - 1LL * (B.y - A.y) * (C.x - A.x);
}
inline LL solve(vector < int > v) {
LL area = 0;
for(int i = 1; i + 1 < v.size(); ++i)
area += cp(a[v[0]], a[v[i]], a[v[i + 1]]);
return abs(area);
}
inline int cmp(pair < int, int> p1, pair < int, int> p2){
return cp(a[1], p1, p2) < 0;
}
void Infasuratoare(vector < int > &v, vector < int > &SOL){
if(v.size() < 3)
return ;
SOL.clear();
SOL.push_back(v[0]);
SOL.push_back(v[1]);
memset(Viz, 0, sizeof(Viz));
Viz[v[1]] = 1;
for(int i = 2 ; i < v.size() ; ++ i) {
if(Viz[v[i]])
continue;
while(SOL.size() >= 2 && cp(a[SOL[SOL.size() - 2]], a[SOL[SOL.size() - 1]], a[v[i]]) < 0) {
Viz[SOL[SOL.size() - 1]] = 0;
SOL.pop_back();
}
Viz[v[i]] = 1;
SOL.push_back(v[i]);
}
for(int i = v.size() - 1 ; i >= 0 ; -- i) {
if(Viz[v[i]])
continue;
while(SOL.size() >= 2 && cp(a[SOL[SOL.size() - 2]], a[SOL[SOL.size() - 1]], a[v[i]]) < 0) {
Viz[SOL[SOL.size() - 1]] = 0;
SOL.pop_back();
}
Viz[v[i]] = 1;
SOL.push_back(v[i]);
}
SOL.pop_back();
}
inline string make_solution(vector < int > Sol3, vector < int > Sol4) {
for(int j = 0 ; j < Sol3.size() ; ++j){
s[0][Sol3[j]] = 'I';
s[1][Sol3[j]] = 'V';
}
for(int j = 0 ; j < Sol4.size() ; ++j){
s[0][Sol4[j]] = 'V';
s[1][Sol4[j]] = 'I';
}
string s1(s[0] + 1);
string s2(s[1] + 1);
return min(s1, s2);
}
int main(){
int n;
freopen("gradina.in", "r", stdin);
ofstream out("gradina.out");
scanf("%d", &n);
for(int i = 1; i <= n; ++i){
int A, B;
scanf("%d %d", &A, &B);
a[i] = make_pair(A, B);
Ind[i] = i;
}
sort(Ind + 1, Ind + n + 1, Cmp);
for(int i = 1; i <= n; ++i)
for(int j = i + 1; j <= n; ++j){
Sol1.clear();
Sol2.clear();
for(int k = 1; k <= n; ++k){
if(k == i)
Sol1.push_back(Ind[k]);
else
if(k == j)
Sol2.push_back(Ind[k]);
else{
if(cp(a[Ind[i]], a[Ind[j]], a[Ind[k]]) > 0)
Sol1.push_back(Ind[k]);
else
Sol2.push_back(Ind[k]);
}
}
Sol3.clear();
Sol4.clear();
Infasuratoare(Sol1, Sol3);
Infasuratoare(Sol2, Sol4);
if(Sol1.size() == Sol3.size() && Sol2.size() == Sol4.size()){
LL Area = fabs(solve(Sol3) - solve(Sol4));
///out << i << ' ' << j << '\n';
if(Area < Min){
Min = Area;
Ans = make_solution(Sol3, Sol4);
}
if(Area == Min)
Ans = min(Ans, make_solution(Sol3, Sol4));
}
}
out << fixed << setprecision(1) << Min * 0.5 << '\n' << Ans << '\n';
return 0;
}