Cod sursa(job #1768176)

Utilizator retrogradLucian Bicsi retrograd Data 30 septembrie 2016 13:30:59
Problema Rubarba Scor 60
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.96 kb
#include <bits/stdc++.h>

using namespace std;

#define ld long double

typedef complex<ld> Point;
const ld kPi = 4.0 * atan(1.0);

const int kMaxN = 100005;
const ld kEps = 1e-8;

ld cross(Point a, Point b) {
	return (conj(a) * b).imag();
}

Point rotatePoint(Point p, ld ang) {
	return p * polar(1.0l, ang);
}

ld rem(ld ang) {
	while(ang < -kEps) ang += 2.0 * kPi;
	while(ang > 2.0l * kPi + kEps) ang -= 2.0l * kPi;
	return ang;
}

struct Caliper {
	Point pivot;
	ld angle;

	ld angleTo(Point oth) {
		ld new_ang = rem(arg(oth - pivot));
		return rem(new_ang - angle);
	}
	void rotateWith(ld ang) {
		angle = rem(angle + ang);
	}

	ld distanceTo(Caliper oth) {
		Point a = rotatePoint(pivot, -angle);
		Point b = rotatePoint(oth.pivot, -angle);

		return abs(a.imag() - b.imag());
	}
};

Point Points[kMaxN];
vector<Point> Hull;

void AddToHull(Point p) {
	while(Hull.size() >= 2) {
		Point a = Hull[Hull.size() - 2];
		Point b = Hull[Hull.size() - 1];

		if(cross(b - a, p - a) < kEps)
			Hull.pop_back();
		else break;
	}
	Hull.push_back(p);
}

int main() {
	freopen("rubarba.in", "r", stdin);
	freopen("rubarba.out", "w", stdout);

	int n;
	cin >> n;
	for(int i = 1; i <= n; ++i) {
		int a, b;
		cin >> a >> b;
		Points[i] = Point(a, b);
	}


	sort(Points + 1, Points + n + 1, [](Point a, Point b) {
		if(a.real() == b.real()) return a.imag() < b.imag();
		return a.real() < b.real();
	});

	for(int i = 1; i < n; ++i) AddToHull(Points[i]);
	for(int i = n; i >= 1; --i) AddToHull(Points[i]);
	Hull.pop_back();


	if(Hull.size() < 3) {
		cout << "0.00\n";
		return 0;
	}

	vector<Caliper> calipers(4);
	vector<int> indices(4, -1);

	for(int ind = 0; ind < Hull.size(); ++ind) {
		if(indices[0] == -1 || Hull[indices[0]].imag() > Hull[ind].imag())
			indices[0] = ind;
		if(indices[1] == -1 || Hull[indices[1]].real() < Hull[ind].real())
			indices[1] = ind;
		if(indices[2] == -1 || Hull[indices[2]].imag() < Hull[ind].imag())
			indices[2] = ind;
		if(indices[3] == -1 || Hull[indices[3]].real() > Hull[ind].real())
			indices[3] = ind;
	}


	for(int i = 0; i < 4; ++i) {
		calipers[i].angle = i * kPi * 0.5;
		calipers[i].pivot = Hull[indices[i]];
	}

	ld ans = 1e18;
	ld totRot = 0.0;
	while(totRot < 4.0 * kPi) {
		ld rot = 4.0 * kPi;
		int choose = -1;

		ld area = calipers[0].distanceTo(calipers[2]) * calipers[1].distanceTo(calipers[3]);
		ans = min(ans, area);

		for(int i = 0; i < 4; ++i) {
			ld ind = indices[i];
			ld 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 << fixed << setprecision(2) << ans << '\n';

	return 0;
}