Pagini recente » Cod sursa (job #3308829) | Cod sursa (job #2272440) | Cod sursa (job #3302713) | Cod sursa (job #1239878) | Cod sursa (job #3338180)
#include <bits/stdc++.h>
using namespace std;
ifstream fin("gradina.in");
ofstream fout("gradina.out");
const int nmax = 255;
double arie(vector<int> a);
bool cmp2(int a, int b);
struct pct
{
long long x, y;
int id;
};
long long triunghi(pct a, pct b, pct c);
bool cmp(pct a, pct b);
pct v[nmax];
int n;
char sol[nmax];
double difmin = DBL_MAX;
int main()
{
fin>>n;
for(int i = 1; i <= n; ++i)
{
fin>>v[i].x>>v[i].y;
v[i].id = i;
sol[i] = 'V';
}
sort(v+1, v+n+1, cmp);
for(int i = 1; i < n; ++i)
{
for(int j = 1; j <= n; ++j)
{
if(i == j)
continue;
vector<int> ion, vasile;
ion.push_back(i);
ion.push_back(j);
for(int k = 1; k <= n; ++k)
{
if(k == i || k == j)
continue;
if(triunghi(v[i], v[j], v[k]) <= 0)
vasile.push_back(k);
else
ion.push_back(k);
}
double arievasile = arie(vasile), arieion = arie(ion);
if(arievasile == 0 || arieion == 0)
continue;
if(abs(arievasile - arieion) < difmin)
{
difmin = abs(arievasile - arieion);
for(auto poz : vasile)
sol[v[poz].id] = 'V';
for(auto poz : ion)
sol[v[poz].id] = 'I';
}
else if(abs(arievasile - arieion) == difmin)
{
char aux[nmax];
for(auto poz : vasile)
aux[v[poz].id] = 'V';
for(auto poz : ion)
aux[v[poz].id] = 'I';
int ind = 1;
while(aux[ind] == sol[ind] && ind <= n)
++ind;
if(ind <= n && aux[ind] == 'I')
{
for(int i = 1; i <= n; ++i)
sol[i] = aux[i];
}
}
}
}
fout<<fixed<<setprecision(1)<<difmin<<"\n";
for(int i = 1; i <= n; ++i)
fout<<sol[i];
return 0;
}
double arie(vector<int> a)
{
if(a.size() < 3)
return 0;
int nr = a.size(), cntsus = 0, cntjos = 0;
vector<int> sus, jos, ch;
sort(a.begin(), a.end(), cmp2);
for(int i = 0; i < nr; ++i)
{
while(cntsus >= 2 && triunghi(v[sus[cntsus-2]], v[sus[cntsus-1]], v[a[i]]) >= 0)
{
--cntsus;
sus.pop_back();
}
while(cntjos >= 2 && triunghi(v[jos[cntjos-2]], v[jos[cntjos-1]], v[a[i]]) <= 0)
{
--cntjos;
jos.pop_back();
}
++cntsus;
++cntjos;
sus.push_back(a[i]);
jos.push_back(a[i]);
}
if(cntsus + cntjos - 2 < nr)
return 0;
for(int i = 0; i < cntjos; ++i)
ch.push_back(jos[i]);
for(int i = cntsus - 2; i >= 1; --i)
ch.push_back(sus[i]);
long long ans = 0;
ans += v[ch[nr-1]].x * v[ch[0]].y - v[ch[nr-1]].y * v[ch[0]].x;
for(int i = 0; i < nr-1; ++i)
{
ans += v[ch[i]].x * v[ch[i+1]].y - v[ch[i]].y * v[ch[i+1]].x;
}
return abs(ans) / 2.0;
}
long long triunghi(pct a, pct b, pct c)
{
return a.x * b.y - a.y * b.x + b.x * c.y - b.y * c.x + c.x * a.y - c.y * a.x;
}
bool cmp2(int a, int b)
{
if(v[a].x == v[b].x)
return (v[a].y < v[b].y);
return (v[a].x < v[b].x);
}
bool cmp(pct a, pct b)
{
if(a.x == b.x)
return (a.y < b.y);
return (a.x < b.x);
}