Pagini recente » Cod sursa (job #1255629) | Cod sursa (job #1620842) | Cod sursa (job #3354187) | Cod sursa (job #3323589) | Cod sursa (job #3339070)
#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;
bitset <NMAX> ion, fina;
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;
}
vector <int> convexhull(vector <int> plan){
int m = plan.size();
if(m < 3) return plan;
vector <int> jos, sus, rez;
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]);
}
for(int a : jos)
rez.push_back(a);
if(sus.size() > 1){
sus.pop_back();
reverse(sus.begin(), sus.end());
sus.pop_back();
for(int a : sus)
rez.push_back(a);
}
return rez;
}
double ariehull(vector <int> hull){
if(hull.size() < 3) return 0;
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);
}
bool verificare(vector<int>& plani, vector<int>& planj){
vector<int> hulli = convexhull(plani);
vector<int> hullj = convexhull(planj);
if(hulli.size() != plani.size() || hullj.size() != planj.size())
return false;
// Verifică separare cu muchii din hull Ion
for(int i=0; i<hulli.size(); i++){
int j = (i+1) % hulli.size();
par a = v[hulli[i]];
par b = v[hulli[j]];
bool ok_vasile = true;
bool ok_ion = true;
for(int p : hullj){
if(arie(a, b, v[p]) > -EPS){
ok_vasile = false;
break;
}
}
for(int p : hulli){
if(p == hulli[i] || p == hulli[j]) continue;
if(arie(a, b, v[p]) < EPS){
ok_ion = false;
break;
}
}
if(ok_vasile && ok_ion)
return true;
}
for(int i=0; i<hullj.size(); i++){
int j = (i+1) % hullj.size();
par a = v[hullj[i]];
par b = v[hullj[j]];
bool ok_ion = true;
bool ok_vasile = true;
for(int p : hulli){
if(arie(a, b, v[p]) > -EPS){
ok_ion = false;
break;
}
}
for(int p : hullj){
if(p == hullj[i] || p == hullj[j]) continue;
if(arie(a, b, v[p]) < EPS){
ok_vasile = false;
break;
}
}
if(ok_ion && ok_vasile)
return true;
}
return false;
}
void backtrack(int poz, bitset<NMAX>& conf, vector<int>& plani, vector<int>& planj){
if(poz > n){
if(plani.size() < 3 || planj.size() < 3)
return;
if(!verificare(plani, planj))
return;
double ariai = ariehull(convexhull(plani));
double ariaj = ariehull(convexhull(planj));
double difa = abs(ariai - ariaj);
if(difa < dif - EPS){
dif = difa;
fina = conf;
} else if(abs(difa - dif) < EPS){
bool mai_bun = false;
for(int i=1; i<=n; i++){
if(conf[i] != fina[i]){
mai_bun = (conf[i] > fina[i]);
break;
}
}
if(mai_bun){
fina = conf;
}
}
return;
}
// Pune în Ion
conf[poz] = 1;
plani.push_back(poz);
backtrack(poz+1, conf, plani, planj);
plani.pop_back();
// Pune în Vasile
conf[poz] = 0;
planj.push_back(poz);
backtrack(poz+1, conf, plani, planj);
planj.pop_back();
}
int main(){
fin >> n;
for(int i=1; i<=n; i++){
fin >> v[i].x >> v[i].y;
v[i].idx = i;
}
bitset<NMAX> conf;
vector<int> plani, planj;
backtrack(1, conf, plani, planj);
fout << fixed << setprecision(1) << dif << '\n';
for(int i=1; i<=n; i++){
fout << (fina[i] ? 'I' : 'V');
}
fout << '\n';
return 0;
}