Cod sursa(job #1768188)

Utilizator retrogradLucian Bicsi retrograd Data 30 septembrie 2016 14:12:07
Problema Rubarba Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.25 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);
}

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

struct Caliper {
	Point pivot;
	double angle;

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

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

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

vector<Point> Points, Hull;

void AddToHull(Point p, vector<Point> &Hull) {
	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);
}
void MakeHull() {
	vector<Point> Up, Down;

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

	for(auto it = Points.begin(); it != Points.end(); ++it)
		AddToHull(*it, Down);
	for(auto it = Points.rbegin(); it != Points.rend(); ++it)
		AddToHull(*it, Up);

	Up.pop_back();
	Down.pop_back();

	for(auto x : Up) Hull.push_back(x);
	for(auto x : Down) Hull.push_back(x);
}

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.emplace_back(a, b);
	}

	MakeHull();

	if(Hull.size() < 3) {
		cout << "0.00\n";
		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 << fixed << setprecision(2) << ans << '\n';

	return 0;
}