Pagini recente » Cod sursa (job #1786573) | Cod sursa (job #1316794) | Cod sursa (job #2838178) | Cod sursa (job #3252788) | Cod sursa (job #2544173)
#include <bits/stdc++.h>
using namespace std;
ifstream fin("gradina.in");
ofstream fout("gradina.out");
struct point{
double x, y;
int poz;
bool operator<(point b){
return x==b.x?y<b.y:x<b.x;
}
point operator- (point a){
return {x-a.x, y-a.y};
}
};
double cp(point o, point a, point b){
a=a-o, b=b-o;
return a.x*b.y-a.y*b.x;
}
double getarea(vector<point> v){
double area=0;
for(int i=1;i<v.size();++i){
area+=cp({0, 0}, v[i-1], v[i]);
}
area+=cp({0, 0}, v[v.size()-1], v[0]);
area=abs(area);
area/=2;
return area;
}
vector<point> hull(vector<point> v){
vector<point> sol;
for(int i=0,p=1;i>=0;i+=(p=i==(v.size()-1)?-p:p)){
while(sol.size()>=2&&cp(sol[sol.size()-2], sol[sol.size()-1], v[i])<0) sol.pop_back();
sol.push_back(v[i]);
}
sol.pop_back();
return sol;
}
void show(vector<point> x){
for(int i=0;i<x.size();++i){
cout<<x[i].x<<" "<<x[i].y<<"\n";
}
}
int main()
{
int n;
fin>>n;
vector<point> x;
for(int i=0;i<n;++i){
point a;
fin>>a.x>>a.y;
a.poz=i;
x.push_back(a);
}
double sol=(1<<30);
string solcode;
sort(x.begin(), x.end());
for(int i=0;i<x.size();++i){
for(int j=0;j<x.size();++j){
if(j==i) continue;
point a, b;
a=x[i];
b=x[j];
vector<point> pa, pb;
string s;
s.resize(n);
for(int k=0;k<x.size();++k){
if(k==i) pa.push_back(a), s[x[k].poz]='I';
else if(k==j) pb.push_back(b), s[x[k].poz]='V';
else{
if(cp(a, b, x[k])>0) pa.push_back(x[k]), s[x[k].poz]='I';
else pb.push_back(x[k]), s[x[k].poz]='V';
}
}
vector<point> hulla=hull(pa);
vector<point> hullb=hull(pb);
if(hulla.size()<pa.size()) continue;
if(hullb.size()<pb.size()) continue;
double dif=abs(getarea(hulla)-getarea(hullb));
if(sol>dif){
sol=dif;
solcode=s;
}
else if(sol==dif){
if(solcode>s) solcode=s;
}
}
}
fout<<fixed<<setprecision(10)<<sol<<"\n";
fout<<solcode<<"\n";
return 0;
}