Pagini recente » Cod sursa (job #1788351) | Cod sursa (job #1132538) | Cod sursa (job #979839) | Cod sursa (job #434616) | Cod sursa (job #1259462)
#include <fstream>
#include <iomanip>
#include <algorithm>
#include <vector>
#include <cmath>
#define lint long long int
#define inf 12100000000000005ll
using namespace std;
struct point{
int x,y;
int poz;
point(int x=0,int y=0, int poz=0): x(x), y(y), poz(poz) {}
};
lint ccw(const point &a,const point &b,const point &c){
return ((a.x-b.x+0ll)*(c.y-b.y)-(a.y-b.y+0ll)*(c.x-b.x));
}
//point centru;
bool operator<(const point &a,const point &b){
//return ccw(a,centru,b)>0;
if(a.x!=b.x)
return a.x<b.x;
return a.y<b.y;
}
bool prost;
vector<point> convex_hull(vector<point> &points){
if(points.size()<=2)
return points;
int n=points.size();//,poz=0;
/*for(int i=0;i<n;i++)
if(points[i].x<points[poz].x || (points[i].x==points[poz].x && points[i].y<points[poz].y))
poz=i;
swap(points[poz],points[0]);
centru=points[0];
sort(points.begin()+1,points.end());*/
vector<point> ans;
ans.push_back(points[0]);
ans.push_back(points[1]);
for(int i=2;i<n;i++){
while(ans.size()>1)
if(ccw(ans[ans.size()-2],ans.back(),points[i])>0)
ans.pop_back();
else
break;
ans.push_back(points[i]);
}
int sz=ans.size()-1;
ans.push_back(points[n-2]);
for(int i=n-3;i>=0;i--){
while(ans.size()+sz>1)
if(ccw(ans[ans.size()-2],ans.back(),points[i])>0)
ans.pop_back();
else
break;
ans.push_back(points[i]);
}
ans.pop_back();
if(ans.size()!=points.size())
prost=true;
return ans;
}
lint arie(vector<point> &points){
lint ans=0;
for(int i=1;i+1<points.size();i++)
ans+=ccw(points[0],points[i],points[i+1]);
return ans;
}
point v[260];
char sir[260];
char rasp[260];
int perm[260];
int main()
{
ifstream cin("gradina.in");
ofstream cout("gradina.out");
int n=0,i,j,k;
cin>>n;
for(int i=1;i<=n;i++){
cin>>v[i].x>>v[i].y;
v[i].poz=i;
}
vector<point> ion,vasile;
lint ans=inf;
sort(v+1,v+n+1);
for(i=1;i<=n;i++)
perm[v[i].poz]=i;
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
if(i!=j){
sir[i]='I';
sir[j]='V';
for(k=1;k<=n;k++)
if(k!=i && k!=j){
if(ccw(v[i],v[j],v[k])>0)
sir[k]='I';
else
sir[k]='V';
}
ion.clear();vasile.clear();
for(k=1;k<=n;k++)
if(sir[k]=='I')
ion.push_back(v[k]);
else
vasile.push_back(v[k]);
prost=false;
vasile=convex_hull(vasile);
ion=convex_hull(ion);
if(prost)
continue;
lint a=arie(ion);
lint b=arie(vasile);
if(abs(a-b)<ans){
if(sir[perm[1]]=='V'){
for(k=1;k<=n;k++)
if(sir[k]=='V')
sir[k]='I';
else
sir[k]='V';
}
ans=abs(a-b);
for(k=1;k<=n;k++)
rasp[k]=sir[k];
}
else if(abs(a-b)==ans){
if(sir[perm[1]]=='V'){
for(k=1;k<=n;k++)
if(sir[k]=='V')
sir[k]='I';
else
sir[k]='V';
}
prost=false;
for(k=1;k<=n;k++)
if(rasp[perm[k]]==sir[perm[k]])
rasp[perm[k]]=sir[perm[k]];
else if(rasp[perm[k]]<sir[perm[k]]){
prost=true;
break;
}
else
break;
if(prost)
continue;
for(;k<=n;k++)
rasp[perm[k]]=sir[perm[k]];
}
}
cout<<fixed<<setprecision(1)<<ans/2.0<<'\n';
for(i=1;i<=n;i++)
cout<<rasp[perm[i]];
cin.close();
cout.close();
return 0;
}