Pagini recente » Profil acc_b_magurele | Cod sursa (job #2402298)
#include <fstream>
#include <cmath>
#include <algorithm>
#include <iomanip>
#define pii pair <int, int>
#define x first
#define y second
using namespace std;
ifstream cin ("rubarba.in");
ofstream cout ("rubarba.out");
int n, vf;
long double area;
pii v[100005], w[100005];
int st[100005];
bool in[100005];
bool orientation(pii a, pii b, pii c) {
return 1LL * (c.y - a.y) * (b.x - a.x) - 1LL * (a.y - b.y) * (a.x - c.x) <= 0;
}
void convex_hull() {
sort(v + 1, v + n + 1);
st[++vf] = 1; st[++vf] = 2;
in[2] = 1;
for(int i = 1, j = 1; i; i += (j = (i == n ? -j : j))) {
if(in[i])
continue;
while(vf > 1 && orientation(v[st[vf - 1]], v[st[vf]], v[i]))
in[st[vf--]] = 0;
st[++vf] = i;
in[st[vf]] = 1;
}
}
long double sqr(long double x) {
return x * x;
}
long double det(pii a, pii b, pii c) {
return 1LL * a.x * b.y + 1LL * a.y * c.x + 1LL * b.x * c.y - 1LL * a.x * c.y - 1LL * a.y * b.x - 1LL * b.y * c.x;
}
int main() {
cin >> n;
for(int i = 1; i <= n; i++)
cin >> v[i].x >> v[i].y;
convex_hull();
vf--;
n = vf;
for(int i = 1; i <= n; i++)
w[i] = v[st[i]];
for(int i = 1; i <= n; i++)
v[i] = w[i];
v[n + 1] = v[1];
area = 1e18;
for(int i = 1; i <= n; i++) {
long double d = sqr(v[i].x - v[i + 1].x) + sqr(v[i].y - v[i + 1].y), hmax = 0, v1 = 0, v2 = 0;
d = sqrt(d);
for(int j = 1; j <= n; j++) {
if(j == i || j == i + 1)
continue;
long double h = abs((long double)det(v[i], v[i + 1], v[j]) / d), ab = sqr(v[i].x - v[j].x) + sqr(v[i].y - v[j].y), ac = sqr(v[i + 1].x - v[j].x) + sqr(v[i + 1].y - v[j].y);
hmax = max(hmax, h);
ab -= sqr(h);
ac -= sqr(h);
if(abs(sqr(d) - ab - ac) <= 1e-12)
continue;
if(ab < ac)
v1 = max(v1, ab);
else
v2 = max(v2, ac);
}
v1 = sqrt(v1); v2 = sqrt(v2);
area = min(area, hmax * (v1 + v2 + d));
}
cout << fixed << setprecision(2) << area;
return 0;
}