Pagini recente » Cod sursa (job #1935685) | Cod sursa (job #3314573) | Cod sursa (job #3356868) | Cod sursa (job #3327439) | Cod sursa (job #3339071)
#include <bits/stdc++.h>
using namespace std;
ifstream fin("gradina.in");
ofstream fout("gradina.out");
const int NMAX = 252;
const double EPS = 1e-9;
int n;
double dif = 1e9;
char fina[NMAX];
struct par{
double x, y;
int idx;
}v[NMAX];
double arie(par a, par b, par c){
return a.x*(b.y-c.y) + b.x*(c.y-a.y) + c.x*(a.y-b.y);
}
bool comp(par a, par b){
if(abs(a.x - b.x) > EPS)
return a.x < b.x;
return a.y < b.y;
}
bool comp_idx(int a, int b){
if(abs(v[a].x - v[b].x) > EPS)
return v[a].x < v[b].x;
return v[a].y < v[b].y;
}
double ariehull(vector<int> plan){
if(plan.size() < 3) return 0;
int m = plan.size();
vector<int> jos, sus, hull;
sort(plan.begin(), plan.end(), comp_idx);
for(int i=0; i<m; i++){
while(jos.size()>1 && arie(v[jos[jos.size()-2]], v[jos[jos.size()-1]], v[plan[i]]) <= 0)
jos.pop_back();
while(sus.size()>1 && arie(v[sus[sus.size()-2]], v[sus[sus.size()-1]], v[plan[i]]) >= 0)
sus.pop_back();
jos.push_back(plan[i]);
sus.push_back(plan[i]);
}
if(jos.size() + sus.size() - 2 < m)
return 0;
for(int a : jos)
hull.push_back(a);
for(int i = sus.size()-2; i >= 1; i--)
hull.push_back(sus[i]);
double aria = 0;
for(int i=0; i<hull.size(); i++){
int j = (i+1) % hull.size();
aria += v[hull[i]].x * v[hull[j]].y;
aria -= v[hull[i]].y * v[hull[j]].x;
}
return abs(aria / 2.0);
}
int main(){
fin >> n;
for(int i=1; i<=n; i++){
fin >> v[i].x >> v[i].y;
v[i].idx = i;
fina[i] = 'V';
}
sort(v+1, v+1+n, comp);
for(int i=1; i<n; i++){
for(int j=1; j<=n; j++){
if(i == j) continue;
vector<int> plani, planj;
plani.push_back(i);
plani.push_back(j);
for(int k=1; k<=n; k++){
if(k == i || k == j)
continue;
if(arie(v[i], v[j], v[k]) <= 0)
planj.push_back(k);
else
plani.push_back(k);
}
double ariai = ariehull(plani);
double ariaj = ariehull(planj);
if(ariai == 0 || ariaj == 0)
continue;
double difa = abs(ariai - ariaj);
if(difa < dif - EPS){
dif = difa;
for(int p : planj)
fina[v[p].idx] = 'V';
for(int p : plani)
fina[v[p].idx] = 'I';
}
else if(abs(difa - dif) < EPS){
char aux[NMAX];
for(int p : planj)
aux[v[p].idx] = 'V';
for(int p : plani)
aux[v[p].idx] = 'I';
int poz = 1;
while(poz <= n && aux[poz] == fina[poz])
poz++;
if(poz <= n && aux[poz] == 'I'){
for(int p=1; p<=n; p++)
fina[p] = aux[p];
}
}
}
}
fout << fixed << setprecision(1) << dif << '\n';
for(int i=1; i<=n; i++)
fout << fina[i];
fout << '\n';
return 0;
}