Pagini recente » Cod sursa (job #9838) | Cod sursa (job #694606) | Cod sursa (job #1071103) | Cod sursa (job #1930291) | Cod sursa (job #2641260)
#include <fstream>
#include <vector>
#include <string>
#include <algorithm>
#include <iomanip>
using namespace std;
const int NMAX = 255;
int det(pair <int, int> a, pair <int, int> b, pair <int, int> c)
{
return (1LL * a.first * b.second + 1LL * b.first * c.second + 1LL * c.first * a.second) - (1LL * b.second * c.first + 1LL * c.second * a.first + 1LL * a.second * b.first);
}
vector < pair <int, int> > ConvexHull(vector <pair <int, int> > hull)
{
vector < pair <int, int> > stk;
stk.push_back(hull[0]);
for (int i = 1; i < hull.size(); ++i)
{
while (stk.size() >= 2 && det(stk[stk.size() - 2], stk[stk.size() - 1], hull[i]) < 0)
stk.pop_back();
stk.push_back(hull[i]);
}
return stk;
}
double Area(vector <pair <int, int> > p)
{
double area = 1LL * p[0].second * p.back().first - 1LL * p[0].first * p.back().second;
for (int i = 0; i < p.size() - 1; ++i)
area += 1LL * p[i].first * p[i + 1].second - 1LL * p[i].second * p[i + 1].first;
area /= 2.0;
return area;
}
int Solve(vector <int> p, vector <pair <int, int> > points)
{
if (p.size() < 3)
return -1;
sort(p.begin(), p.end(), [&](int i, int j)
{
if (points[i].first == points[j].first)
return points[i].second < points[j].second;
return points[i].first < points[j].first;
});
vector <pair <int, int> > underHull;
vector <pair <int, int> > aboveHull;
underHull.push_back(points[p[0]]);
aboveHull.push_back(points[p[0]]);
for (int i = 1; i < p.size() - 1; ++i)
{
if (det(points[p[0]], points[p[i]], points[p.back()]) >= 0)
underHull.push_back(points[p[i]]);
else
aboveHull.push_back(points[p[i]]);
}
underHull.push_back(points[p.back()]);
aboveHull.push_back(points[p.back()]);
reverse(aboveHull.begin(), aboveHull.end());
int szUnderHull = underHull.size();
int szAboveHull = aboveHull.size();
underHull = ConvexHull(underHull);
aboveHull = ConvexHull(aboveHull);
if (underHull.size() != szUnderHull || aboveHull.size() != szAboveHull)
return -1;
underHull.pop_back();
aboveHull.pop_back();
vector <pair <int, int> > hull;
for (auto& i : underHull)
hull.push_back(i);
for (auto& i : aboveHull)
hull.push_back(i);
if (hull.size() == p.size())
return Area(hull);
return -1;
}
int main()
{
ifstream fin("gradina.in");
ofstream fout("gradina.out");
int N;
fin >> N;
vector < pair <int, int> > points(N);
for (int i = 0; i < N; ++i)
fin >> points[i].first >> points[i].second;
double answerDiff = -1;
string answer(N, '0');
for (int i = 0; i < N; ++i)
for (int j = 0; j < N; ++j)
if (i != j)
{
vector <int> p1, p2;
for (int k = 0; k < N; ++k)
{
if (i == k)
p1.push_back(k);
else if (j == k)
p2.push_back(k);
else
{
if (det(points[i], points[k], points[j]) >= 0)
p1.push_back(k);
else
p2.push_back(k);
}
}
double area1 = Solve(p1, points);
double area2 = Solve(p2, points);
if (area1 != -1 && area2 != -1)
{
double diff = area1 - area2;
if (diff < 0)
diff *= -1; ///nu mai am voie cu abs? :(
string aux(N, 'V');
for (auto& k : p1)
aux[k] = 'I';
if (aux[0] == 'V')
{
for (auto& k : aux)
{
if (k == 'I')
k = 'V';
else
k = 'I';
}
}
if (answerDiff == -1 || diff < answerDiff || (diff == answerDiff && aux < answer))
{
answerDiff = diff;
answer = aux;
}
}
}
fout << setprecision(1) << fixed;
fout << answerDiff << "\n";
fout << answer << "\n";
fin.close();
fout.close();
return 0;
}