Pagini recente » Cod sursa (job #2330232) | Cod sursa (job #21456) | Termeni si conditii de utilizare a site-ului infoarena | Cod sursa (job #2986475) | Cod sursa (job #1844579)
#include <cstdio>
#include <cmath>
#include <vector>
#include <algorithm>
using namespace std;
#define EPS (1.0E-10)
struct L {
double x, y;
};
int N;
vector<L> v;
L ll;
vector<L> hull;
/*bool cmp(L l1, L l2) {
return atan2(ll.y - l1.y, ll.x - l1.x) > atan2(ll.y - l2.y, ll.x - l2.x);
}*/
double ccw(L a, L b, L c) {
return (b.x - a.x) * (c.y - a.y) - (c.x - a.x) * (b.y - a.y);
}
bool cmp(L a, L b) {
return ccw(ll, a, b) > -EPS;
}
double dist(L a, L b) {
return (a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y);
}
L norm(L a) {
L tmp;
double d = sqrt(a.x * a.x + a.y * a.y);
tmp = a;
tmp.x /= d;
tmp.y /= d;
return tmp;
}
L rotate(L w, L by) {
L tmp;
tmp.x = w.x * by.x + w.y * by.y;
tmp.y = - w.y * by.x + w.x * by.y;
return tmp;
}
L subt(L a, L b) {
L tmp;
tmp.x = a.x - b.x;
tmp.y = a.y - b.y;
return tmp;
}
int main() {
int i, j;
freopen("rubarba.in", "r", stdin);
freopen("rubarba.out", "w", stdout);
scanf("%d", &N);
if(N <= 2) {
printf("0.00\n");
return 0;
}
j = 0;
ll.x = 1.0E10;
ll.y = 1.0E10;
for(i = 0; i < N; i++) {
int x, y;
scanf("%d %d", &x, &y);
L tmp;
tmp.x = x;
tmp.y = y;
if(tmp.x < ll.x) {
ll.x = tmp.x;
ll.y = tmp.y;
j = i;
} else if(tmp.x == ll.x && tmp.y < ll.y) {
ll.x = tmp.x;
ll.y = tmp.y;
j = i;
}
v.push_back(tmp);
}
L tmp = v[0];
v[0] = v[j];
v[j] = tmp;
sort(v.begin() + 1, v.end(), cmp);
hull.push_back(v[0]);
hull.push_back(v[1]);
for(i = 2; i < v.size(); i++) {
while(hull.size() > 1 && ccw(hull[hull.size() - 2], hull[hull.size() - 1], v[i]) < EPS) {
hull.pop_back();
}
hull.push_back(v[i]);
}
double mina = 1.0E15;
for(i = 0; i < hull.size(); i++) {
double mx, Mx, my, My;
L s;
if(i != 0) {
s = norm(subt(hull[i - 1], hull[i]));
} else {
s = norm(subt(hull[0], hull.back()));
}
L crt = rotate(hull[0], s);
mx = Mx = crt.x;
my = My = crt.y;
for(j = 1; j < hull.size(); j++) {
crt = rotate(hull[j], s);
if(mx > crt.x) {
mx = crt.x;
}
if(Mx < crt.x) {
Mx = crt.x;
}
if(my > crt.y) {
my = crt.y;
}
if(My < crt.y) {
My = crt.y;
}
}
if((Mx - mx) * (My - my) < mina) {
mina = (Mx - mx) * (My - my);
}
}
printf("%.2lf\n", mina);
return 0;
}