Pagini recente » Cod sursa (job #302113) | Cod sursa (job #260161) | Cod sursa (job #3136961) | Cod sursa (job #2373128) | Cod sursa (job #1262593)
#include <cstdio>
#include <vector>
#include <string>
#include <cstring>
#include <algorithm>
#include <fstream>
#include <iomanip>
#define x first
#define y second
#define LL long long
using namespace std;
const int nmax=250;
int n;
LL Min=(1<<30);
string Ans;
char c[2][nmax+5];
pair < int, int > a[nmax+5];
vector < int > sol1, sol2, sol_i, sol_v;
int ind[nmax+5];
bool viz[nmax+5];
bool cmp(int ind1, int ind2)
{
return a[ind1].x < a[ind2].x || (a[ind1].x == a[ind2].x && a[ind1].y < a[ind2].y);
}
int ll;
LL myabs(LL x)
{
if(x>0)return x;
return -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);
}
bool cmp2(int ind1, int ind2)
{
return cp(a[ll], a[ind1], a[ind2])>0;
}
LL area(vector < int > v)
{
int A=0;
for(int i=1;i<v.size()-1;i++)
A+=cp(a[v[0]], a[v[i]], a[v[i+1]]);
return myabs(A);
}
void convex_hull(vector <int> &ind, vector <int> &sol)
{
ll=ind[0];
sort(ind.begin(), ind.end(), cmp2);
if(ind.size()<3)return;
sol.clear();
sol.push_back(ind[0]);
sol.push_back(ind[1]);
memset(viz, 0, sizeof(viz));
viz[ind[1]]=true;
for(int i=2;i<ind.size();i++)
{
if(viz[ind[i]])continue;
while(sol.size()>=2 && cp(a[sol[sol.size()-2]], a[sol[sol.size()-1]], a[ind[i]])<0)
{
viz[sol[sol.size()-1]]=false;
sol.pop_back();
}
viz[ind[i]]=true;
sol.push_back(ind[i]);
}
}
string make_string(vector < int > v, vector < int > i)
{
for(int j=0;j<v.size();j++)
{
c[0][v[j]]='I';
c[1][v[j]]='V';
}
for(int j=0;j<i.size();j++)
{
c[0][i[j]]='V';
c[1][i[j]]='I';
}
string s1(c[0]+1);
string s2(c[1]+1);
return min(s1, s2);
}
int main()
{
freopen("gradina.in", "r", stdin);
ofstream out("gradina.out");
scanf("%d", &n);
for(int i=1;i<=n;i++)
{
scanf("%d%d", &a[i].first, &a[i].second);
ind[i]=i;
}
sort(ind+1, ind+n+1, cmp);
for(int i=1;i<=n;i++)
{
for(int j=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]);
}
sol_i.clear();
sol_v.clear();
convex_hull(sol1, sol_i);
convex_hull(sol2, sol_v);
if(sol1.size()==sol_i.size() && sol2.size()==sol_v.size())
{
LL Ai=area(sol_i);
LL Av=area(sol_v);
LL dif=myabs(Ai-Av);
if(dif<Min)
{
Min=dif;
Ans=make_string(sol_i, sol_v);
}
else if(dif==Min)
{
Ans=min(Ans, make_string(sol_i, sol_v));
}
}
}
}
out << fixed << setprecision(1) << Min*0.5 << "\n" << Ans << "\n";
return 0;
}