Cod sursa(job #2051501)

Utilizator teoionescuIonescu Teodor teoionescu Data 29 octombrie 2017 01:50:53
Problema Rubarba Scor 70
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.44 kb
#include <bits/stdc++.h>
using namespace std;

const double pi = 4.*atan(1);
const double eps = 1e-6;

struct point {
	double x, y;
};
struct line {
	double a, b;
};
typedef complex<double> comp;

double ccw(point a, point b, point c) {
	return a.x*b.y - a.y*b.x + b.x*c.y - b.y*c.x + c.x*a.y - c.y*a.x;
}

double dist(point a, point b) {
	return sqrt((a.x-b.x)*(a.x-b.x) + (a.y-b.y)*(a.y-b.y));
}

int eq(double d1,double d2) {
	return abs(d1-d2) < eps;
}

line fromPoints(point p1, point p2) {
	double a = (p1.y - p2.y) / (p1.x - p2.x);
	return {a, p1.y - a*p1.x};
}

point inters(line l1, line l2) {
	double x = (l2.b - l1.b) / (l1.a - l2.a);
	return {x, l1.a*x + l1.b};
}

line perpend(line l, point gp) {
	return {double(-1)/l.a, gp.y + gp.x/l.a};
}

point proiect(point p, line l) {
	return inters(l, perpend(l, p));
}

void rotate(vector<double> &xr, vector<double> &yr) {
	double t = 2*pi/1e5;
	comp w = {cos(t), sin(t)};
	for(int i=0; i<(int)xr.size(); i++) {
		comp cr = w * (comp){xr[i], yr[i]};
		xr[i]=real(cr);
		yr[i]=imag(cr);
	}
}

vector<int> chull(vector<double> &xr, vector<double> &yr) {
	int n = xr.size();
	vector<int> v(n);
	for(int i=0; i<n; i++) v[i] = i;
	sort(v.begin(), v.end(), [&xr, &yr](const int &i, const int &j) {
		if(eq(xr[i], xr[j])) {
			return yr[i] < yr[j];
		}
		return xr[i] < xr[j];
	});
	int i1 = v[0];
	swap(v[0], v[n-1]);
	v.pop_back();
	sort(v.begin(), v.end(), [i1, &xr, &yr](const int &i, const int &j) {
		return ccw((point){xr[i1], yr[i1]}, (point){xr[i],yr[i]}, (point){xr[j], yr[j]}) > 0.;
	});
	vector<int> cs;
	cs.push_back(i1);
	for(auto it : v) {
		while(cs.size() >= 2 && 
			ccw(
				(point){xr[cs[cs.size()-2]], yr[cs[cs.size()-2]]},
				(point){xr[cs[cs.size()-1]],yr[cs[cs.size()-1]]}, 
				(point){xr[it], yr[it]}) < 0.) {
			cs.pop_back();
		}
		cs.push_back(it);
	}
	return cs;
}

int cb(int st, int dr, function<double(int)> const& f) {
	int i = st, pas=1<<18;
	while(pas) {
		if(i+pas<dr && f(i+pas) < f(i+pas+1)) i+=pas;
		pas>>=1;
	}
	if(f(i+pas) < f(i+pas+1)) {
		return i+1;
	}
	return i;
}

int main() {
	freopen("rubarba.in", "r", stdin);
	freopen("rubarba.out", "w", stdout);
	vector<double> xr, yr;
	int n;
	
	cin>>n;
	xr.resize(n);
	yr.resize(n);
	for(int i=0; i<n; i++) {
		cin>>xr[i]>>yr[i];
	}
	rotate(xr, yr);
	vector<int> hulls = chull(xr, yr);
	int hn = (int)hulls.size();
	for(int i=0; i<hn; i++) {
		hulls.push_back(hulls[i]);
	}
	double ans = n < 3 ? 0. : 1e100;
	for(int i=0; i<hn; i++) {
		point p1 = (point){xr[hulls[i]], yr[hulls[i]]};
		point p2 = (point){xr[hulls[i+1]], yr[hulls[i+1]]};
		line l = fromPoints(p1, p2);
		int w = cb(i+1, i+hn, [&xr, &yr, &l, &hulls](const int &i) -> double {
			point p = {xr[hulls[i]], yr[hulls[i]]};
			return dist(p, proiect(p, l));
		});
		point pw = {xr[hulls[w]], yr[hulls[w]]};
		int drw = cb(i+1, w, [&xr, &yr, &l, &hulls, &pw](const int &i) -> double {
			point p = {xr[hulls[i]], yr[hulls[i]]};
			return dist(proiect(pw, l), proiect(p, l));
		});
		int stw = cb(w, i+hn, [&xr, &yr, &l, &hulls, &pw](const int &i) -> double {
			point p = {xr[hulls[i]], yr[hulls[i]]};
			return dist(proiect(pw, l), proiect(p, l));
		});
		point pstw = {xr[hulls[stw]], yr[hulls[stw]]};
		double stwidth = dist(proiect(pw, l), proiect(pstw, l));

		point pdrw = {xr[hulls[drw]], yr[hulls[drw]]};
		double drwidth = dist(proiect(pw, l), proiect(pdrw, l));

		double height = dist(pw, proiect(pw, l));
		ans = min(ans, (stwidth + drwidth) * height);
	}
	cout.precision(2);
	cout<<fixed<<ans<<'\n';
	return 0;
}