Cod sursa(job #713767)

Utilizator eukristianCristian L. eukristian Data 14 martie 2012 22:13:05
Problema Rubarba Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 4.63 kb
#include <stdio.h>
#include <algorithm>
#include <float.h>
#include <stdlib.h>
#include <math.h>

#define MAXN 100001
using namespace std;

typedef struct {
	int x;
	int y;
} Vector2i;

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 rotatic_calipers();

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();
	rotatic_calipers();
	
	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 rotatic_calipers()
{
	double minarea = DBL_MAX;
	Vector2i *vect = (Vector2i *) malloc(sizeof(Vector2i) * (ch[0] + 1));
	double* inv_vect_length = (double *) malloc(sizeof(double) * (ch[0] + 1));
	int left = 1, right = 1, top = 1, bottom = 1;
	int seq[] = {-1, -1, -1, -1};
		
	Vector2i pt0 = {coord[ch[1]][0], coord[ch[1]][1]};
	
	int left_x = pt0.x, right_x = pt0.x;
	int top_y = pt0.y, bottom_y = pt0.y;
	
	for (int i = 1 ; i <= ch[0] ; ++i)
	{
		int dx, dy;
		
		if (left_x > pt0.x)
			left_x = pt0.x, left = i;
		if (right_x < pt0.x)
			right_x = pt0.x, right = i;
		if (top_y < pt0.y)
			top_y = pt0.y, top = i;
		if (bottom_y > pt0.y)
			bottom_y = pt0.y, bottom = i;
			
		int newIndex = (i + 1 <= ch[0] ? (i + 1) : 1);
		Vector2i pt = {coord[ch[newIndex]][0], coord[ch[newIndex]][1]};
		
		dx = pt.x - pt0.x;
		dy = pt.y - pt0.y;
		
		vect[i].x = dx;vect[i].y = dy;
		inv_vect_length[i] = (double)(1.0 / sqrt((double)dx * dx + (double)dy * dy));
		
		pt0 = pt;
	}
	
	double base_a = 1, base_b = 0;
	/* calipers coordinates : (a, b), (-b, a), (-a, -b), (b, -a)*/
	seq[0] = bottom;
	seq[1] = right;
	seq[2] = top;
	seq[3] = left;
	
	for (int k = 1 ; k <= ch[0] ; ++k)
	{
		double dp0 = base_a * vect[seq[0]].x + base_b * vect[seq[0]].y;
        double dp1 = -base_b * vect[seq[1]].x + base_a * vect[seq[1]].y;
        double dp2 = -base_a * vect[seq[2]].x - base_b * vect[seq[2]].y;
        double dp3 = base_b * vect[seq[3]].x - base_a * vect[seq[3]].y;
        
        double cosalpha = dp0 * inv_vect_length[seq[0]];
        double maxcos = cosalpha;
        
        int main_element = 0;
        
        cosalpha = dp1 * inv_vect_length[seq[1]];
        maxcos = (cosalpha > maxcos) ? (main_element = 1, cosalpha) : maxcos;
        cosalpha = dp2 * inv_vect_length[seq[2]];
        maxcos = (cosalpha > maxcos) ? (main_element = 2, cosalpha) : maxcos;
        cosalpha = dp3 * inv_vect_length[seq[3]];
        maxcos = (cosalpha > maxcos) ? (main_element = 3, cosalpha) : maxcos;
        
        int pindex = seq[main_element];
        double lead_x = vect[pindex].x * inv_vect_length[pindex];
        double lead_y = vect[pindex].y * inv_vect_length[pindex];
        
        switch (main_element)
        {
			case 0:
				base_a = lead_x;
				base_b = lead_y;
				break;
			case 1:
				base_a = lead_y;
				base_b = -lead_x;
				break;
			case 2:
                base_a = -lead_x;
                base_b = -lead_y;
                break;
            case 3:
                base_a = -lead_y;
                base_b = lead_x;
                break;
		}
		
        seq[main_element] += 1;
        seq[main_element] = (seq[main_element] == ch[0] + 1) ? 1 : seq[main_element];
        
        double height, area, width, dx, dy;
        
        dx = coord[ch[seq[1]]][0] - coord[ch[seq[3]]][0];
        dy = coord[ch[seq[1]]][1] - coord[ch[seq[3]]][1];
        
        width = dx * base_a + dy * base_b;
        
        dx = coord[ch[seq[2]]][0] - coord[ch[seq[0]]][0];
        dy = coord[ch[seq[2]]][1] - coord[ch[seq[0]]][1];
        
        height = -dx * base_b + dy * base_a;
        area = width * height;
        
        if (area < minarea)
			minarea = area;
	}
	
    free( vect );
    free( inv_vect_length );
    
    printf("%.2f\n", minarea);
}