Pagini recente » Cod sursa (job #379070) | Cod sursa (job #1537488) | Cod sursa (job #78356) | Cod sursa (job #2959290) | Cod sursa (job #3248169)
#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <iomanip>
#include <string>
#define pdd pair<double, double>
using namespace std;
ifstream in("gradina.in");
ofstream out("gradina.out");
const int NMAX = 250;
int n;
pair<pdd, int> v[NMAX];
bool cmp(const pair<pdd, int>& a, const pair<pdd, int>& b)
{
if(a.first.first < b.first.first)
{
return 1;
}
if(a.first.first == b.first.first)
{
return a.first.second < b.first.second;
}
if(a.first.first > b.first.first)
{
return 0;
}
return 0;
}
double arie(pdd A, pdd B, pdd C)
{
return ((A.first * B.second + B.first * C.second + C.first * A.second)
-(C.first * B.second + A.first * C.second + B.first * A.second)) / 2;
}
double infasoara(pdd pct[], int len)
{
int stiva[NMAX];
bool tip[NMAX];
for(int i=1; i<len-1; i++)
{
if(arie(pct[0], pct[len-1], pct[i]) < 0)
{
tip[i] = 0;
}
else
{
tip[i] = 1;
}
}
int vf = 0;
stiva[vf] = 0;
for(int i=1; i<len; i++)
{
if(i==len-1 || tip[i] == 0)
{
while(vf > 0 && arie(pct[stiva[vf-1]], pct[stiva[vf]], pct[i]) < 0)
{
vf--;
return -1; //e concav
}
vf++;
stiva[vf] = i;
}
}
int last_size = vf;
for(int i=len-2; i>=0; i--)
{
if(i == 0 || tip[i] == 1)
{
while(vf > last_size && arie(pct[stiva[vf-1]], pct[stiva[vf]], pct[i]) < 0)
{
vf--;
return -1; //e concav
}
vf++;
stiva[vf] = i;
}
}
if(vf < 3)//nu exista poligon cu mai putin de 3 varfuri
{
return -1;
}
double area = 0;
for(int i=1; i<vf-1; i++)
{
area += abs(arie(pct[0], pct[stiva[i]], pct[stiva[i+1]]));
}
return abs(area);
}
void solve()
{
double ariemin = 100000000;
string solmin(NMAX, 'Z');
for(int i=0; i<n; i++)
{
for(int j=i+1; j<n; j++)
{
bool tip[NMAX];
string temp(NMAX, 'Z');
for(int k=0; k<n; k++)
{
tip[k] = (arie(v[i].first, v[j].first, v[k].first) >= 0);
if(tip[k] == 0)
{
temp[v[k].second] = 'I';
}
else
{
temp[v[k].second] = 'V';
}
}
tip[i] = 0; temp[v[i].second] = 'I';
tip[j] = 1; temp[v[j].second] = 'V';
if(v[j].second < v[i].second)
{
tip[i] = 1; temp[v[i].second] = 'V';
tip[j] = 0; temp[v[j].second] = 'I';
}
pdd v1[NMAX], v2[NMAX];
int n1=0, n2=0;
for(int k=0; k<n; k++)
{
if(tip[k] == 0)
{
v1[n1++] = v[k].first;
}
else
{
v2[n2++] = v[k].first;
}
}
if(n1 >= 3 && n2 >= 3) //nu exista poligon cu mai putin de 3 varfuri
{
double area1 = infasoara(v1, n1);
double area2 = infasoara(v2, n2);
if(area1 != -1 && area2 != -1)
{
double area = abs(area1-area2);
if(area < ariemin)
{
ariemin = area;
solmin = temp;
}
if(area == ariemin)
{
if(temp < solmin)
{
solmin = temp;
}
}
}
}
}
}
out<<fixed<<setprecision(1)<<ariemin<<"\n";
for(int i=0; i<n; i++)
{
out<<solmin[i];
}
}
int main()
{
in>>n;
for(int i=0; i<n; i++)
{
double x,y;
in>>x>>y;
v[i] = {{x,y}, i};
}
sort(v, v+n, cmp);
solve();
return 0;
}