Pagini recente » Sandbox (cutiuţa cu năsip) | Cod sursa (job #3183851) | Cod sursa (job #505259) | Cod sursa (job #1122243) | Cod sursa (job #2402606)
#include <fstream>
#include <algorithm>
#include <iomanip>
#include <cmath>
#define pii pair <long double, long double>
#define x first
#define y second
using namespace std;
ifstream cin ("rubarba.in");
ofstream cout ("rubarba.out");
const long double EPS = 1e-16;
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 (c.y - a.y) * (b.x - a.x) - (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 abs(a.x * b.y + a.y * c.x + b.x * c.y - a.x * c.y - a.y * b.x - b.y * c.x);
}
long double dist(pii a, pii b) {
return sqr(a.x - b.x) + sqr(a.y - b.y);
}
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 = 1e12;
for(int i = 1; i <= n; i++) {
long double hmax = 0, v1 = 0, v2 = 0, ab, ac, d2 = dist(v[i], v[i + 1]);
for(int j = 1; j <= n; j++) {
if(j == i || j == i + 1)
continue;
long double h = (long double)det(v[i], v[i + 1], v[j]) / d2 * det(v[i], v[i + 1], v[j]);
if(h > hmax)
hmax = h;
ab = dist(v[i], v[j]) - h; ac = dist(v[i + 1], v[j]) - h;
if(ab - d2 <= EPS && ac - d2 <= EPS)
continue;
if(ab <= ac) {
if(ab > v1)
v1 = ab;
} else {
if(ac > v2)
v2 = ac;
}
}
v1 = sqrtl(v1); v2 = sqrtl(v2); hmax = sqrtl(hmax); d2 = sqrtl(d2);
area = min(area, hmax * (v1 + v2 + d2));
}
cout << fixed << setprecision(2) << area;
return 0;
}