Pagini recente » Cod sursa (job #2675607) | Cod sursa (job #1104908) | Cod sursa (job #2414426) | Cod sursa (job #412206) | Cod sursa (job #1862515)
#include <fstream>
#include <cmath>
#include <algorithm>
#include <iomanip>
#define DIM 100010
using namespace std;
struct punct {
double x;
double y;
punct (double x, double y) {
this->x = x;
this->y = y;
}
punct () {
this->x = 0;
this->y = 0;
}
};
punct p[DIM], s[DIM];
double minim = 1000000000000LL;
int n, k;
double det(const punct &a, const punct &b, const punct &c) {
return (b.x-a.x)*(c.y-a.y) - (c.x-a.x)*(b.y-a.y);
}
int cmp( const punct &a, const punct &b ) {
return det(p[1], a, b) > 0;
}
inline int next(int i) {
return (i==k?1:i+1);
}
inline int prev(int i) {
return (i==1?k:i-1);
}
punct piciorPerpendiculara(punct a, punct b, punct c) {
// piciorul perpendicularei din c pe dreapta ab
if (a.y == b.y) {
punct r(c.x, a.y);
return r;
}
if (a.x == b.x) {
punct r(a.x, c.y);
return r;
}
double M = (b.y - a.y)/(b.x - a.x);
double B1 = ( a.y * (b.x - a.x) - a.x * (b.y - a.y) ) / (b.x - a.x);
double B2 = c.y + c.x/M;
punct r;
r.x = M * (B2 - B1) / (M*M + 1);
r.y = M * r.x + B1;
return r;
}
double patratDistantaPuncte(punct a, punct b) {
return (a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y);
}
double distPunctDereapta(punct a, punct b, punct c) {
double A= det(a, b, c);
if (A < 0)
A = -A;
double D = patratDistantaPuncte(a, b);
return A/sqrt(D);
}
int main () {
ifstream fin ("rubarba.in");
ofstream fout("rubarba.out");
fin>>n;
double minim = 1000001;
for (int i=1;i<=n;i++) {
fin>>p[i].x>>p[i].y;
}
int poz = 1;
for (int i=2;i<=n;i++) {
if ( (p[i].y < p[poz].y) || ( (p[i].y == p[poz].y) && (p[i].x < p[poz].x) ) )
poz = i;
}
punct aux = p[1];
p[1] = p[poz];
p[poz] = aux;
for (int i=2;i<=n;i++) {
p[i].x -= p[1].x;
p[i].y -= p[1].y;
}
p[1].x = p[1].y = 0;
sort(p+2, p+n+1, cmp);
s[1] = p[1];
s[2] = p[2];
k = 2;
for (int i=3; i<=n; i++) {
while (k >= 2 && det(s[k-1], s[k], p[i]) <= 0 )
k--;
s[++k] = p[i];
}
int a = 2, b = 2, c = 2;
punct ra, rn;
for (int i=1;i<=k;i++) {
a = next(i);
ra = piciorPerpendiculara(s[i], s[next(i)], s[a]);
do {
rn = piciorPerpendiculara(s[i], s[next(i)], s[next(a)]);
if ( (rn.x-ra.x) * (ra.x-s[i].x) > 0 ) {
a = next(a);
ra = rn;
}
else
break;
} while (1);
punct r1 = ra;
b = a;
double da, dn;
da = distPunctDereapta(s[i], s[next(i)], s[b]);
do {
dn = distPunctDereapta(s[i], s[next(i)], s[next(b)]);
if (dn > da) {
b = next(b);
da = dn;
} else
break;
} while (1);
c = i;
ra = piciorPerpendiculara(s[i], s[next(i)], s[c]);
do {
rn = piciorPerpendiculara(s[i], s[next(i)], s[prev(c)]);
if ( (ra.x-s[next(i)].x) * (rn.x - ra.x) > 0) {
c = prev(c);
ra = rn;
}
else
break;
} while (1);
punct r2 = ra;
if (sqrt(patratDistantaPuncte(r1, r2)) * distPunctDereapta(s[i], s[next(i)], s[b]) < minim) {
minim = sqrt(patratDistantaPuncte(r1, r2)) * distPunctDereapta(s[i], s[next(i)], s[b]);
}
}
fout<<setprecision(2)<<fixed<<minim;
return 0;
}