Cod sursa(job #1033210)

Utilizator scipianusFMI Ciprian Olariu scipianus Data 16 noiembrie 2013 16:34:09
Problema Rubarba Scor 70
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.25 kb
#include <fstream>
#include <cmath>
#include <cstdio>
#include <algorithm>
#include <cstdlib>
#include <cassert>
#define EPS 0.0000001
#define INF 1000000000000.0
#define PI 3.14159265359
using namespace std;
int n, vf, ord[100100];
long long dist[100100];
double Cos, Sin, sol = INF;
struct Punct{int x, y; };
Punct P[100100], St[100100], O;
struct Punct2{double x, y; };
char *buffer;

inline long long Dist(Punct A, Punct B)
{
	return 1LL * (A.x - B.x) * (A.x - B.x) + 1LL * (A.y - B.y) * (A.y - B.y);
}

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

inline bool Sortare(int a, int b)
{
	if(abs(Panta(P[a], P[1]) - Panta(P[b], P[1])) < EPS)
		return dist[a] < dist[b];
	return Panta(P[a], P[1]) > Panta(P[b], P[1]);
}

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

inline void NextInt(int &x)
{
    while(*buffer < '0' || '9' < *buffer)
        buffer++;
    x = 0;
    while('0' <= *buffer && *buffer <= '9')
    {
        x = x * 10 + *buffer - '0';
        buffer++;
    }
}

inline void Read()
{
	int i;
	ifstream fin("rubarba.in");
    fin.seekg(0, ios::end);
    int fs = fin.tellg();
    fin.seekg(0, ios::beg);
    buffer = (char *)malloc(fs);
    fin.getline(buffer, fs, 0);
    fin.close();
	
	NextInt(n);
	for(i = 1; i <= n; ++i)
	{
		NextInt(P[i].x);
		NextInt(P[i].y);
	}
}

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]);
	for(i = 2; i <= n; ++i)
	{
		dist[i] = Dist(P[i], P[1]);
		ord[i] = i;
	}
	sort(ord + 2, ord + n + 1, Sortare);
	St[++vf] = P[1];
	for(i = 2; i <= n; ++i)
	{
		while(vf >= 2 && Intoarcere(St[vf - 1], St[vf], P[ord[i]]) >= 0LL)
			vf--;
		St[++vf] = P[ord[i]];
	}
	for(i = 1; i <= vf; ++i)
		P[i] = St[i];
	P[vf + 1] = P[1];
	n = vf;
}

inline Punct2 Rotate(Punct P0)
{
	// roteste in sens trigonometric pe P0 cu alfa radiani in jurul lui O
    Punct2 P1;
    P1.x = 1.0 * O.x + 1.0 * (P0.x - O.x) * Cos - 1.0 * (P0.y - O.y) * Sin;
    P1.y = 1.0 * O.y + 1.0 * (P0.x - O.x) * Sin + 1.0 * (P0.y - O.y) * Cos;
    return P1;
}

inline void Solve()
{
	int i, j;
	double alfa, xmax, xmin, ymax, ymin;
	Punct2 newP;
	for(i = 1; i <= n; ++i)
	{
		// iau pe rand fiecare latura a infasuratorii convexe
		// ca fiind o latura a bounding-box-ului
		alfa = 2.0 * PI - Panta(P[i], P[i + 1]);
		Sin = sin(alfa);
		Cos = cos(alfa);
		O = P[i];
		xmax = ymax = -INF;
		xmin = ymin = INF;
		// rotesc punctele in jurul lui P[i]
		// ca sa determin mai usor punctele extreme ale bounding-box-ului
		for(j = 1; j <= n; ++j)
		{
			newP = Rotate(P[j]);
			xmax = max(xmax, newP.x);
			xmin = min(xmin, newP.x);
			ymax = max(ymax, newP.y);
			ymin = min(ymin, newP.y);
		}
		// si sa pot afla astfel aria pentru a actualiza 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;
}