Cod sursa(job #1768168)

Utilizator retrogradLucian Bicsi retrograd Data 30 septembrie 2016 13:18:47
Problema Rubarba Scor 60
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.92 kb
#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 * kPi);
	}
	void rotateWith(double ang) {
		angle = remainder(angle + ang, 2 * kPi);
	}

	double 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) <= 0)
			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 = remainder(i * kPi * 0.5, 2.0 * kPi);
		calipers[i].pivot = Hull[indices[i]];
	}

	double ans = 1e18;
	double totRot = 0.0;
	while(totRot < 4.0 * kPi) {
		double rot = 4.0 * 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 << fixed << setprecision(2) << ans << '\n';

	return 0;
}