Pagini recente » Cod sursa (job #2407386) | Cod sursa (job #1101330) | Cod sursa (job #288874) | Rating NeroLuci (nero_luci) | Cod sursa (job #2446961)
#include <fstream>
#include <vector>
#include <algorithm>
#include <math.h>
#include <iomanip>
using namespace std;
ifstream fin("rubarba.in");
ofstream fout("rubarba.out");
const int NMAX = 1e5;
struct Punct
{
long long x, y;
};
struct Dreapta
{
long double a, b, c;
};
int N;
Punct v[NMAX + 5];
vector <Punct> hull;
Dreapta dreapta(Punct p1, Punct p2)
{
Dreapta d1 = {p2.y - p1.y, p1.x - p2.x, p1.y * p2.x - p1.x * p2.y};
long double aux = sqrt((long double)d1.a * d1.a + d1.b * d1.b);
long double k = 1 / aux;
d1.a *= k;
d1.b *= k;
d1.c *= k;
return d1;
}
Dreapta perp(Punct a, Dreapta d)
{
Dreapta d1 = {-d.b, d.a, d.b * a.x - d.a * a.y};
long double aux = sqrt((long double)d1.a * d1.a + d1.b * d1.b);
long double k = 1 / aux;
d1.a *= k;
d1.b *= k;
d1.c *= k;
return d1;
}
long double distd(Punct a, Dreapta d)
{
return a.x * d.a + a.y * d.b + d.c;
}
long long cross_product(Punct P1, Punct P2, Punct P3)
{
return (P2.x - P1.x) * (P3.y - P1.y) -
(P2.y - P1.y) * (P3.x - P1.x);
}
inline bool cmp(const Punct A, const Punct B)
{
return cross_product(v[1], A, B) < 0;
}
void ReadAndHull()
{
fin >> N;
int x, y;
for(int i = 1; i <= N; i++)
{
fin >> x >> y;
v[i] = {x, y};
}
for(int i = 2; i <= N; i++)
if((v[i].x == v[1].x && v[i].y < v[1].y) || v[i].x < v[1].x)
swap(v[1], v[i]);
sort(v + 2, v + N + 1, cmp);
hull.push_back(v[1]);
for(int i = 2; i <= N; i++)
{
while (hull.size() > 1 && cross_product(hull[hull.size() - 2], hull[hull.size() - 1], v[i]) >= 0)
hull.pop_back();
hull.push_back(v[i]);
}
}
const long double INF = 2000000000;
void Solve()
{
long double ans = 100 * INF;
for(int i = 0; i < hull.size(); i++)
{
long double di1, di2, di3;
di1 = di2 = -INF;
di3 = INF;
Dreapta d1;
if(i == hull.size() - 1)
d1 = dreapta(hull[hull.size() - 1], hull[0]);
else
d1 = dreapta(hull[i], hull[i + 1]);
Dreapta d2 = perp(hull[i], d1);
for (long long j = 0; j < hull.size(); ++j)
{
long double dist1 = fabs(distd(hull[j], d1));
long double dist2 = distd(hull[j], d2);
if (di1 < dist1)
di1 = dist1;
if (di2 < dist2)
di2 = dist2;
if (di3 > dist2)
di3 = dist2;
}
long double dst = di2 - di3;
ans = min(ans, dst * di1);
}
fout << fixed << setprecision(3) << ans << '\n';
}
int main()
{
ReadAndHull();
Solve();
return 0;
}