Pagini recente » Cod sursa (job #355676) | Cod sursa (job #1921855) | Cod sursa (job #2641229) | Cod sursa (job #657476) | Cod sursa (job #2975302)
#include <fstream>
#include <vector>
#include <algorithm>
#include <string>
#include <iostream>
#include <iomanip>
#include <climits>
#pragma GCC optimize ("O1")
#pragma GCC optimize ("O2")
#pragma GCC optimize ("O3")
#pragma GCC optimize ("Ofast")
#pragma GCC optimize ("unroll-loops")
using namespace std;
ifstream in ("gradina.in");
ofstream out ("gradina.out");
const double eps = 1e-3;
const int max_size = 251;
#define ll long long
struct pdd {
double first, second;
};
pdd mult1[max_size], mult2[max_size], v[max_size];
vector <pdd> chhhh;
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 cmp1 (pdd x, pdd y)
{
return orientare(mult1[1], x, y) < 0;
}
bool cmp2 (pdd x, pdd y)
{
return orientare(mult2[1], x, y) < 0;
}
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.push_back('I');
}
else
{
mult2[++pct2] = v[i];
curr.push_back('V');
}
}
if (pct1 < 3 || pct2 < 3)
{
return false;
}
chhhh.clear();
sort(mult1 + 1, mult1 + pct1 + 1, cmp1);
chhhh.push_back(mult1[1]);
chhhh.push_back(mult1[2]);
for (int i = 3; i <= pct1; i++)
{
while (chhhh.size() > 1 && orientare(chhhh[chhhh.size() - 2], chhhh[chhhh.size() - 1], mult1[i]) >= 0)
{
return false;
}
chhhh.push_back(mult1[i]);
}
chhhh.clear();
sort(mult2 + 1, mult2 + pct2 + 1, cmp2);
chhhh.push_back(mult2[1]);
chhhh.push_back(mult2[2]);
for (int i = 3; i <= pct2; i++)
{
while (chhhh.size() > 1 && orientare(chhhh[chhhh.size() - 2], chhhh[chhhh.size() - 1], mult2[i]) >= 0)
{
return false;
}
chhhh.push_back(mult2[i]);
}
return true;
}
double arie1 ()
{
double ans = 0;
for (int i = 3; i <= pct1; i++)
{
ans += orientare(mult1[1], mult1[i - 1], mult1[i]) / 2;
}
return ans;
}
double arie2 ()
{
double ans = 0;
for (int i = 3; i <= pct2; i++)
{
ans += orientare(mult2[1], mult2[i - 1], mult2[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;
}
out << fixed << setprecision(1);
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();
double anou = abs(a1 - a2);
if (abs(anou - ans) < eps && curr < minimuuu)
{
ans = anou;
minimuuu = curr;
}
else
{
if (anou < ans)
{
ans = anou;
minimuuu = curr;
}
}
//cout << ans << " " << minimuuu << '\n';
}
}
}
out << ans << '\n' << minimuuu;
in.close();
out.close();
return 0;
}