Pagini recente » Cod sursa (job #1837533) | Cod sursa (job #1760349) | Cod sursa (job #3203564) | Cod sursa (job #1834844) | Cod sursa (job #182557)
Cod sursa(job #182557)
#include <cstdio>
#include <cmath>
#include <algorithm>
using namespace std;
#define MAX_N 1000
#define inf 0x3f3f3f3f
struct punct {
int x, y;
punct(int a, int b) { x=a, y=b; }
punct() { x=y=0; }
bool operator<(punct B) {
return y<B.y || (y==B.y && x<B.x);
}
} P[MAX_N];
int n, i, j;
int H[MAX_N], v;
struct comp {
bool operator()(punct A, punct B) {
long long x1 = A.x-P[0].x, x2 = B.x-P[0].x;
long long y1 = A.y-P[0].y, y2 = B.y-P[0].y;
if ( x1*y2==x2*y1 )
return A<B;
return x1*y2-x2*y1 > 0;
}
};
bool test(punct A, punct B, punct C) {
long long x1 = B.x-A.x, x2 = C.x-A.x;
long long y1 = B.y-A.y, y2 = C.y-A.y;
return x1*y2 - x2*y1 > 0;
}
void convex() {
sort(P+1, P+n, comp());
H[0] = 0, H[1] = 1, H[2] = 2, v=2;
for ( i=3; i<n; ++i ) {
while ( !test(P[H[v-1]], P[H[v]], P[i]) && v>=2 )
--v;
H[++v] = i;
}
++v;
}
int main() {
freopen("rubarba.in", "r", stdin);
freopen("rubarba.out", "w", stdout);
scanf("%d", &n);
int m = 0;
for ( i=0; i<n; ++i ) {
scanf("%d %d", &P[i].x, &P[i].y);
if ( P[i]<P[m] ) m = i;
}
swap(P[m], P[0]);
convex();
H[v] = H[0];
double Aria = 1./0;
for ( i=0; i<v; ++i ) {
double m1 = (1.*P[H[i+1]].y-P[H[i]].y)/(1.*P[H[i+1]].x-P[H[i]].x);
double m2 = -1/m1;
double c11 = 1./0, c12 = -1./0, c21 = 1./0, c22 = -1./0;
double x, y;
if ( fabs(m1) < 0.001 || fabs(m2) < 0.001 ) {
for ( j=0; j<v; ++j ) {
c11 = min(c11, 1.*P[H[j]].x); c12 = max(c12, 1.*P[H[j]].x);
c21 = min(c21, 1.*P[H[j]].y); c22 = max(c22, 1.*P[H[j]].y);
}
x = c12-c11, y = c22-c21;
} else {
for ( j=0; j<v; ++j ) {
double c1 = P[H[j+1]].y*1.-(P[H[j]].x)?m1*P[H[j]].x:0;
double c2 = P[H[j+1]].y*1.-(P[H[j]].x)?m2*P[H[j]].x:0;
c11 = min(c1, c11); c12 = max(c1, c12);
c21 = min(c2, c21); c22 = max(c2, c22);
}
x = (c12-c11)/sqrt(1+1/(m1*m1));
y = (c22-c21)/sqrt(1+1/(m2*m2));
}
double act = x*y;
if ( act<Aria ) Aria = act;
}
printf("%.2lf\n", Aria);
return 0;
}