Pagini recente » Cod sursa (job #1985152) | Cod sursa (job #440549) | Cod sursa (job #1810101) | Cod sursa (job #118576) | Cod sursa (job #2975289)
#include <fstream>
#include <vector>
#include <algorithm>
#include <string>
#include <iostream>
#include <iomanip>
using namespace std;
ifstream in ("gradina.in");
ofstream out ("gradina.out");
const double eps = 1e-3;
const int max_size = 251;
#define pdd pair <double, double>
#define ll long long
pdd mult1[max_size], mult2[max_size], ch1[max_size], ch2[max_size], v[max_size];
vector <pdd> jos, sus;
int n, pct1, pct2, rez1, rez2;
string curr;
double orientare (pdd x, pdd y, pdd z)
{
return (double)((ll)x.first * (y.second - z.second) + (ll)y.first * (z.second - x.second) + (ll)z.first * (x.second - y.second));
}
bool ch (int x, int y)
{
curr.clear();
pct1 = 0;
pct2 = 0;
for (int i = 1; i <= n; i++)
{
if (orientare(v[x], v[y], v[i]) < 0)
{
mult1[++pct1] = v[i];
curr += 'I';
}
else
{
mult2[++pct2] = v[i];
curr += 'V';
}
}
if (pct1 < 3 || pct2 < 3)
{
return false;
}
sus.clear();
jos.clear();
sort(mult1 + 1, mult1 + pct1 + 1);
sus.push_back(mult1[1]);
jos.push_back(mult1[1]);
for (int i = 2; i <= pct1; i++)
{
while (sus.size() > 1 && orientare(sus[sus.size() - 2], sus[sus.size() - 1], mult1[i]) >= 0)
{
sus.pop_back();
}
while (jos.size() > 1 && orientare(jos[jos.size() - 2], jos[jos.size() - 1], mult1[i]) <= 0)
{
jos.pop_back();
}
sus.push_back(mult1[i]);
jos.push_back(mult1[i]);
}
sus.pop_back();
reverse(sus.begin(), sus.end());
sus.pop_back();
rez1 = 0;
for (auto f : jos)
{
ch1[++rez1] = f;
}
for (auto f : sus)
{
ch1[++rez1] = f;
}
if (rez1 != pct1)
{
return false;
}
sus.clear();
jos.clear();
sort(mult2 + 1, mult2 + pct2 + 1);
sus.push_back(mult2[1]);
jos.push_back(mult2[1]);
for (int i = 2; i <= pct2; i++)
{
if (sus.size() > 1 && orientare(sus[sus.size() - 2], sus[sus.size() - 1], mult2[i]) >= 0)
{
sus.pop_back();
}
if (jos.size() > 1 && orientare(jos[jos.size() - 2], jos[jos.size() - 1], mult2[i]) <= 0)
{
jos.pop_back();
}
sus.push_back(mult2[i]);
jos.push_back(mult2[i]);
}
sus.pop_back();
reverse(sus.begin(), sus.end());
sus.pop_back();
rez2 = 0;
for (auto f : jos)
{
ch2[++rez2] = f;
}
for (auto f : sus)
{
ch2[++rez2] = f;
}
if (rez2 != pct2)
{
return false;
}
return true;
}
double arie1 ()
{
double ans = 0;
for (int i = 3; i <= pct1; i++)
{
ans += orientare(ch1[1], ch1[i - 1], ch1[i]) / 2;
}
return ans;
}
double arie2 ()
{
double ans = 0;
for (int i = 3; i <= pct2; i++)
{
ans += orientare(ch2[1], ch2[i - 1], ch2[i]) / 2;
}
return ans;
}
int main ()
{
string minimuuu = "X";
double ans = 1e9 + 1;
in >> n;
for (int i = 1; i <= n; i++)
{
in >> v[i].first >> v[i].second;
}
for (int i = 1; i <= n; i++)
{
for (int j = 1; j <= n; j++)
{
if (i == j)
{
continue;
}
if (ch(i, j))
{
double a1 = arie1(), a2 = arie2();
//cout << a1 << " " << a2 << " " << curr << '\n';
if (abs(abs(a1 - a2) - ans) < eps && curr < minimuuu)
{
ans = abs(a1 - a2);
minimuuu = curr;
}
else
{
if (abs(a1 - a2) < ans)
{
ans = abs(a1 - a2);
minimuuu = curr;
}
}
//cout << ans << " " << minimuuu << '\n';
}
}
}
out << ans << '\n' << minimuuu;
in.close();
out.close();
return 0;
}