Cod sursa(job #1033184)

Utilizator scipianusFMI Ciprian Olariu scipianus Data 16 noiembrie 2013 16:06:41
Problema Rubarba Scor 70
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.47 kb
#include <fstream>
#include <cmath>
#include <cstdio>
#include <algorithm>
#define EPS 0.0000001
#define INF 1000000000000.0
#define PI 3.14159265359
using namespace std;
int n, vf;
double sol = INF;
struct Punct{double x, y; };
Punct P[100100], St[100100];

inline double Dist(Punct A, Punct B)
{
	return sqrt((A.x - B.x) * (A.x - B.x) + (A.y - B.y) * (A.y - B.y));
}

inline double Panta(Punct A, Punct B)
{
	return atan2(A.y - B.y, A.x - B.x);
}

inline bool Sortare(Punct A, Punct B)
{
	if(abs(Panta(A, P[1]) - Panta(B, P[1])) < EPS)
		return Dist(A, P[1]) < Dist(B, P[1]);
	return Panta(A, P[1]) > Panta(B, P[1]);
}

inline double Intoarcere(Punct A, Punct B, Punct C)
{
    return (A.x * B.y + B.x * C.y + C.x * A.y - C.x * B.y - B.x * A.y - A.x * C.y);
}

inline void Read()
{
	int i;
	ifstream fin("rubarba.in");
	fin >> n;
	for(i = 1; i <= n; ++i)
		fin >> P[i].x >> P[i].y;
	fin.close();
}

inline void MakeItConvex()
{
	int i, P0 = 1;
	for(i = 2; i <= n; ++i)
		if(P[i].y < P[P0].y || (P[i].y == P[P0].y && P[i].x < P[P0].x))
			P0 = i;
	swap(P[1], P[P0]);
	sort(P + 2, P + n + 1, Sortare);
	St[++vf] = P[1];
	for(i = 2; i <= n; ++i)
	{
		while(vf >= 2 && Intoarcere(St[vf - 1], St[vf], P[i]) >= 0.0)
			vf--;
		St[++vf] = P[i];
	}
	for(i = 1; i <= vf; ++i)
		P[i] = St[i];
	P[vf + 1] = P[1];
	n = vf;
}

inline Punct Rotate(Punct P0, Punct O, double alfa)
{
	// roteste in sens trigonometric pe P0 cu alfa radiani in jurul lui O
    Punct P1;
    P1.x = O.x + (P0.x - O.x) * cos(alfa) - (P0.y - O.y) * sin(alfa);
    P1.y = O.y + (P0.x - O.x) * sin(alfa) + (P0.y - O.y) * cos(alfa);
    return P1;
}

inline void Solve()
{
	int i, j;
	double alfa, xmax, xmin, ymax, ymin;
	Punct newP;
	for(i = 1; i <= n; ++i)
	{
		// iau pe rand fiecare latura a infasuratorii convexe
		// ca fiind o latura a bounding-box-ului
		alfa = Panta(P[i], P[i + 1]);
		xmax = ymax = -INF;
		xmin = ymin = INF;
		// determin punctele extreme ale bounding-box-ului
		for(j = 1; j <= n; ++j)
		{
			newP = Rotate(P[j], P[i], 2.0 * PI - alfa);
			xmax = max(xmax, newP.x);
			xmin = min(xmin, newP.x);
			ymax = max(ymax, newP.y);
			ymin = min(ymin, newP.y);
		}
		// ca sa pot afla aria si sa actualizez solutia
		sol = min(sol, (xmax - xmin) * (ymax - ymin));
	}
}

inline void Write()
{
	freopen("rubarba.out", "w", stdout);
	printf("%.3lf\n", sol);
}

int main()
{
	Read();
	MakeItConvex();
	Solve();
	Write();
	return 0;
}