Cod sursa(job #713791)

Utilizator eukristianCristian L. eukristian Data 14 martie 2012 22:53:23
Problema Rubarba Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.12 kb
#include <cstdio>
#include <algorithm>
#include <cfloat>
#include <cmath>
#define MAXN 100001
using namespace std;


int n, coord[MAXN][2], points[MAXN], btLeft;
int ch[MAXN];

bool compare(const int &a, const int &b)
{
	return (coord[a][0] - coord[btLeft][0]) * (coord[b][1] - coord[btLeft][1]) 
		> (coord[a][1] - coord[btLeft][1]) * (coord[b][0] - coord[btLeft][0]);
}

bool ccwTurn(int p1, int p2, int p3)
{
	return (coord[p2][0] - coord[p1][0]) * (coord[p3][1] - coord[p1][1]) > (coord[p2][1] - coord[p1][1]) * (coord[p3][0] - coord[p1][0]);
}

void convex_hull();
void solve();

int main()
{
	freopen("rubarba.in", "r", stdin);
	freopen("rubarba.out","w",stdout);
	
	scanf("%d", &n);
	coord[btLeft][0] = coord[btLeft][1] = 0x7fffffff;
	
	for (int i = 1 ; i <= n ; ++i)
	{
		scanf("%d %d", &coord[i][0], &coord[i][1]);
		if (coord[i][1] < coord[btLeft][1] || (coord[i][1] == coord[btLeft][1] && coord[i][0] < coord[btLeft][0]))
			btLeft = i;
	}
	convex_hull();
	solve();
	
	return 0;
}

void convex_hull()
{
	for (int i = 1 ; i <= n ; ++i)
		if (i != btLeft)
			points[++points[0]] = i;
	
	sort(points + 1, points + points[0] + 1, compare);
	
	ch[0] = 3;
	ch[1] = btLeft;
	ch[2] = points[1];
	ch[3] = points[2];
	
	for (int i = 3 ; i <= points[0] ; ++i)
	{
		while (!ccwTurn(ch[ch[0] - 1], ch[ch[0]], points[i]))
			ch[0]--;
		ch[++ch[0]] = points[i] ;
	}
	
}

void solve()
{
	double minarea = DBL_MAX;
	ch[ch[0] + 1] = ch[1];
	
	for (int i = 1 ; i <= ch[0] ; ++i)
	{
		double vx = coord[ch[i + 1]][0] - coord[ch[i]][0];
		double vy = coord[ch[i + 1]][1] - coord[ch[i]][1];
		
		double len = sqrt(vx * vx + vy * vy);
		vx /= len;vy /= len;
		
		double px = vy, py = -vx;
		double s0 = 0, s1 = 0, t0 = 0, t1 = 0;
		for (int j = 1 ; j <= ch[0] ; ++j)
		{
			int ux = coord[ch[j]][0] - coord[ch[i]][0];
			int uy = coord[ch[j]][1] - coord[ch[i]][1];
			double test = ux * vx + uy * vy;
			if (test < s0) s0 = test;
			else if (test > s1) s1 = test;
			
			test = ux * px + uy * py;
			if (test < t0) t0 = test;
			else if (test > t1) t1 = test;
		}
		
		double area = (s1 - s0) * (t1 - t0);
		if (area < minarea)
			minarea = area;
	}
	
	printf("%.2f\n", minarea);
}