Cod sursa(job #1746803)

Utilizator TimitocArdelean Andrei Timotei Timitoc Data 23 august 2016 22:27:20
Problema Rubarba Scor 90
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.15 kb
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <vector>
#define MAXN 100050
#define DINF 5e200

using namespace std;

const double EPS = 0.00000000008;
bool equals(double e, double f)
{
    return (e-f) > -EPS && (e-f) < EPS;
}
struct punct
{
    double x, y;
    punct(double x = 0, double y = 0) : x(x), y(y) { }
    bool operator()(punct e, punct f)
    {
    	if (!equals(e.x, f.x))
			return e.x < f.x;
		return e.y < f.y;
    }
};

int n;
punct a[MAXN];
vector<punct> infas, s2;

void citire()
{
	scanf("%d", &n);
	for (int i = 1; i <= n; i++)
		scanf("%lf %lf", &a[i].x, &a[i].y);
}

inline double det(punct e, punct f, punct g)
{
	return e.x*f.y + f.x*g.y + g.x*e.y - g.x*f.y - f.x*e.y - e.x*g.y;
}

void add(vector<punct> &v, punct e)
{
	while (v.size() > 1  && det(v[v.size()-2], v.back(), e) < 0)
		v.pop_back();
	v.push_back(e);
}

void filtru()
{
	sort(a+1, a+n+1, punct());
	infas.push_back(a[1]);
	for (int i = 2; i <= n; i++) {
		add(infas, a[i]);
	}
	s2.push_back(a[n]);
	for (int i = n-1; i >= 1; i--) {
        add(s2, a[i]);
	}
	infas.pop_back();
	//s2.pop_back();
	for (punct e : s2)
		infas.push_back(e);
//    for (punct e : infas) {
//        printf("%lf %lf\n", e.x, e.y);
//    }
}

double dist(punct e, punct f)
{
    return sqrt((e.x-f.x)*(e.x-f.x) + (e.y-f.y)*(e.y-f.y));
}

void solve()
{
	double arie = DINF;
    for (int i = 0; i < infas.size()-1; i++) {
		punct e = infas[i];
		punct f = infas[i+1];
		if (equals(e.x, f.x) && equals(e.y, f.y)) continue;
        double cs = (f.x-e.x) / dist(e, f);
        double sn = -(f.y-e.y) / dist(e, f);
        double minx = DINF, maxx=-DINF, miny=DINF, maxy=-DINF;
        for (int j = 0; j < infas.size()-1; j++) {
            double xprim = infas[j].x * cs - infas[j].y * sn;
            double yprim = infas[j].y * cs + infas[j].x * sn;
			minx = min(minx, xprim);
			miny = min(miny, yprim);
			maxx = max(maxx, xprim);
			maxy = max(maxy, yprim);
        }
        double crt = (maxx-minx)*(maxy-miny);
		if (crt < arie)
			arie = crt;
    }
	printf("%.2lf", arie);
}

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

	citire();
	filtru();
	solve();

    return 0;
}