Cod sursa(job #1173914)

Utilizator ELHoriaHoria Cretescu ELHoria Data 21 aprilie 2014 02:39:32
Problema Rubarba Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.98 kb
#include <vector>
#include <string>
#include <algorithm>
#include <iostream>
#include <functional>
#include <limits>
#include <cmath>
#define EPS 1e-12

using namespace std;


tuple<double, double, int> mostfar(vector< pair<double, double> >& hull,int j, int n, double s, double c, double mx, double my) {// advance j to extreme pair<double, double>
    double xn, yn;
	double rx, ry;
	double x, y;
	tie(xn, yn) = hull[j];
	rx = xn*c - yn*s;
	ry = xn*s + yn*c;
	double best = mx*rx + my*ry;
	while (1) {
		x = rx;
		y = ry;
		tie(xn, yn) = hull[(j + 1) % n];
		rx = xn*c - yn*s;
		ry = xn*s + yn*c;
		if (mx*rx + my*ry >= best) {
			j = (j + 1) % n;
			best = mx*rx + my*ry;
		} else {
			return make_tuple( x, y, j );
		}
	}
	return make_tuple(0.0,0.0,0);
}

double solve(vector< pair<double, double> >& hull) {
	double ret = numeric_limits<double>::max();
	int n = hull.size();
	int iL, iR, iP;
	double xP, yP;
	double xR, yR;
	double xL, yL;
	iL = iR = iP = 1;
	double pi = 4 * atan(1);
	for (int i = 0; i < n - 1; i++) {
		double dx = hull[i + 1].first - hull[i].first;
		double dy = hull[i + 1].second - hull[i].second;
		double theta = pi - atan2(dy, dx);
		double s = sin(theta);
		double c = cos(theta);
		double yC = hull[i].first * s + hull[i].second * c;
		tie(xP, yP, iP) = mostfar(hull, iP, n, s, c, 0, 1);
		if (i == 0) iR = iP;
		tie(xR, yR, iR) = mostfar(hull, iR, n, s, c, 1, 0);
		tie(xL, yL, iL) = mostfar(hull, iL, n, s, c, -1, 0);
		double area = (yP - yC) * (xR - xL);
		ret = area + EPS < ret ? area : ret;
		//printf("%d %d %d %d %.5lf\n", i, iL, iP, iR, area);
	}

	return ret;
}

double crossProduct(pair<double, double>& A, pair<double, double>& O, pair<double, double>& B) {
	return (A.first - O.first) * (B.second - O.second) - (B.first - O.first) * (A.second - O.second);
}

vector< pair<double, double > > convexHull(vector< pair<double, double> >& points) {
	vector< pair<double, double > > ret;
	sort(points.begin(), points.end());
	int n = points.size();
	vector<int> st(points.size());
	vector<bool> vis(points.size());
	st[0] = 0; st[1] = 1; 
	int head = 2;
	vis[1] = true;
	for (int i = 0, p = 1; i >= 0; i += (p = (i == n - 1 ? -p : p))) {
		if (vis[i]) continue;
		while (head >= 2 && crossProduct(points[st[head - 2]], points[st[head - 1]], points[i]) < EPS)
			vis[st[--head]] = false;
		st[head++] = i;
		vis[i] = true;
	}

	for (int i = 0; i < head - 1; ++i) {
		ret.push_back({ points[st[i]].first, points[st[i]].second });
	}

	return ret;
}

void readData(vector< pair<double, double> >& points) {
	int n;
	scanf("%d", &n);
	points.resize(n);
	for (int i = 0; i < n; i++) {
		scanf("%lf %lf", &points[i].first, &points[i].second);
	}
}

int main()
{
	freopen("rubarba.in", "r", stdin);
	freopen("rubarba.out", "w", stdout);
	vector< pair<double,double> > points;
	vector< pair<double, double> > hull;
	readData(points);
	hull = convexHull(points);
	printf("%.2lf\n",solve(hull));
	return 0;
}