Pagini recente » Cod sursa (job #1893769) | Cod sursa (job #492362) | Cod sursa (job #1009489) | Cod sursa (job #1790158) | Cod sursa (job #1746805)
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <vector>
#include <iomanip>
#define MAXN 100050
#define DINF 5e200
using namespace std;
const long double EPS = 0.00000000008;
bool equals(long double e, long double f)
{
return (e-f) > -EPS && (e-f) < EPS;
}
struct punct
{
long double x, y;
punct(long double x = 0, long double y = 0) : x(x), y(y) { }
bool operator()(punct e, punct f)
{
if (!equals(e.x, f.x))
return e.x < f.x;
return e.y < f.y;
}
};
int n;
punct a[MAXN];
vector<punct> infas, s2;
void citire()
{
cin >> n;
for (int i = 1; i <= n; i++)
cin >> a[i].x >> a[i].y;
}
inline long double det(punct e, punct f, punct g)
{
return e.x*f.y + f.x*g.y + g.x*e.y - g.x*f.y - f.x*e.y - e.x*g.y;
}
void add(vector<punct> &v, punct e)
{
while (v.size() > 1 && det(v[v.size()-2], v.back(), e) < 0)
v.pop_back();
v.push_back(e);
}
void filtru()
{
sort(a+1, a+n+1, punct());
infas.push_back(a[1]);
for (int i = 2; i <= n; i++) {
add(infas, a[i]);
}
s2.push_back(a[n]);
for (int i = n-1; i >= 1; i--) {
add(s2, a[i]);
}
infas.pop_back();
//s2.pop_back();
for (punct e : s2)
infas.push_back(e);
// for (punct e : infas) {
// printf("%lf %lf\n", e.x, e.y);
// }
}
long double dist(punct e, punct f)
{
return sqrt((e.x-f.x)*(e.x-f.x) + (e.y-f.y)*(e.y-f.y));
}
void solve()
{
long double arie = DINF;
for (int i = 0; i < infas.size()-1; i++) {
punct e = infas[i];
punct f = infas[i+1];
if (equals(e.x, f.x) && equals(e.y, f.y)) continue;
long double cs = (f.x-e.x) / dist(e, f);
long double sn = -(f.y-e.y) / dist(e, f);
long double minx = DINF, maxx=-DINF, miny=DINF, maxy=-DINF;
for (int j = 0; j < infas.size()-1; j++) {
long double xprim = infas[j].x * cs - infas[j].y * sn;
long double yprim = infas[j].y * cs + infas[j].x * sn;
minx = min(minx, xprim);
miny = min(miny, yprim);
maxx = max(maxx, xprim);
maxy = max(maxy, yprim);
}
long double crt = (maxx-minx)*(maxy-miny);
if (crt < arie)
arie = crt;
}
cout << fixed << setprecision(2) << arie;
}
int main()
{
freopen("rubarba.in", "r", stdin);
freopen("rubarba.out", "w", stdout);
citire();
filtru();
solve();
return 0;
}