Pagini recente » Cod sursa (job #1778181) | Cod sursa (job #1335502) | Cod sursa (job #2124257) | Cod sursa (job #275159) | Cod sursa (job #2053642)
#include <bits/stdc++.h>
using namespace std;
typedef complex<double> Point;
const double kPi = 4.0 * atan(1.0);
const int kMaxN = 100005;
const double kEps = 1e-8;
double cross(Point a, Point b) {
return (conj(a) * b).imag();
}
Point rotatePoint(Point p, double ang) {
return p * polar(1.0, ang);
}
struct Caliper {
Point pivot;
double angle;
double angleTo(Point oth) {
double new_ang = arg(oth - pivot);
return remainder(new_ang - angle, 2.0 * kPi);
}
void rotateWith(double ang) {
angle = remainder(angle + ang, 2.0 * kPi);
}
double distanceTo(Caliper oth) {
Point a = rotatePoint(pivot, -angle);
Point b = rotatePoint(oth.pivot, -angle);
return abs(a.imag() - b.imag());
}
};
template<typename IT>
vector<Point> MakeLowerEnvelope(IT b, IT e) {
vector<Point> Hull;
for(auto it = b; it != e; ++it) {
while(Hull.size() >= 2) {
Point a = Hull[Hull.size() - 2];
Point b = Hull[Hull.size() - 1];
if(cross(b - a, (*it) - a) < kEps)
Hull.pop_back();
else break;
}
Hull.push_back(*it);
}
Hull.pop_back();
return Hull;
}
vector<Point> MakeHull(vector<Point> &Points) {
sort(Points.begin(), Points.end(), [](Point a, Point b) {
if(a.real() == b.real()) return a.imag() < b.imag();
return a.real() < b.real();
});
auto Hull = MakeLowerEnvelope(Points.begin(), Points.end());
auto Up = MakeLowerEnvelope(Points.rbegin(), Points.rend());
copy(Up.begin(), Up.end(), back_inserter(Hull));
return Hull;
}
int main() {
freopen("rubarba.in", "r", stdin);
freopen("rubarba.out", "w", stdout);
cout << fixed << setprecision(2);
int n;
cin >> n;
vector<Point> Points;
for(int i = 1; i <= n; ++i) {
int a, b;
cin >> a >> b;
Points.emplace_back(a, b);
}
auto Hull = MakeHull(Points);
if(Hull.size() < 3) {
cout << 0 << endl;
return 0;
}
vector<Caliper> calipers(4);
vector<int> indices(4, -1);
auto cmpx = [](Point a, Point b) {return a.real() < b.real();};
auto cmpy = [](Point a, Point b) {return a.imag() < b.imag();};
indices[0] = min_element(Hull.begin(), Hull.end(), cmpy) - Hull.begin();
indices[1] = max_element(Hull.begin(), Hull.end(), cmpx) - Hull.begin();
indices[2] = max_element(Hull.begin(), Hull.end(), cmpy) - Hull.begin();
indices[3] = min_element(Hull.begin(), Hull.end(), cmpx) - Hull.begin();
for(int i = 0; i < 4; ++i) {
calipers[i].angle = i * kPi * 0.5;
calipers[i].pivot = Hull[indices[i]];
}
double ans = 1e18;
double totRot = 0.0;
while(totRot < 2.1 * kPi) {
double rot = 2.1 * kPi;
int choose = -1;
double area = calipers[0].distanceTo(calipers[2]) * calipers[1].distanceTo(calipers[3]);
ans = min(ans, area);
for(int i = 0; i < 4; ++i) {
double ind = indices[i];
double dang = calipers[i]
.angleTo(Hull[(indices[i] + 1) % Hull.size()]);
if(rot > dang) {
rot = dang;
choose = i;
}
}
for(int i = 0; i < 4; ++i)
calipers[i].rotateWith(rot);
indices[choose] = (indices[choose] + 1) % Hull.size();
assert(calipers[choose].angleTo(Hull[indices[choose]]) < kEps);
calipers[choose].pivot = Hull[indices[choose]];
totRot += rot;
}
cout << ans << endl;
return 0;
}