Cod sursa(job #553002)

Utilizator BuRNB Radu BuRN Data 13 martie 2011 13:04:27
Problema Infasuratoare convexa Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.47 kb
#include <cstdio>
#include <cmath>
#include <algorithm>
using namespace std;

#define nmax 10001
int n, poz, st[nmax], vf;

struct punct
{
	float x, y;
	float up;
}p[nmax];

bool cmp(punct a, punct b)
{ return a.up < b.up; }

void push(int x)
{ st[++vf] = x; }

void pop()
{ vf--; }

void citire()
{
	freopen("infasuratoare.in","r",stdin); scanf("%d", &n);
	for(int i=1; i<=n; i++)
		scanf("%f %f", &p[i].x, &p[i].y);
}

void afisare()
{
	freopen("infasuratoare.out","w",stdout);
	printf("%d\n", vf);
	
	while(vf)
	{
		printf("%f %f\n", p[st[vf]].x, p[st[vf]].y);
		pop();
	}
	
}

void caut_pmin()
{
	poz = 1;
	for(int i=1; i<=n; i++)
		if(p[i].y <= p[poz].y)
			if(p[i].y < p[poz].y || p[i].x < p[poz].x)
				poz = i;
}

float dist(int i)
{
	return cos( abs(p[poz].x-p[i].x) / sqrt( pow(p[poz].x-p[i].x, float(2))+pow(p[poz].y-p[i].y, float(2)) ) );
}

void unghi_p()
{
	for(int i=1; i<=n; i++)
		if(i==poz)
			p[i].up = 0;
		else
			p[i].up = dist(i);
}


int directie(int p1, int p2, int p3)
{
	return (p[p2].x-p[p1].x)*(p[p3].y-p[p1].y) - (p[p3].x-p[p1].x)*(p[p2].y-p[p1].y);
}

void solve()
{
	caut_pmin();
	unghi_p();
	sort(p+1, p+1+n, cmp);

	push(1); push(2);
	for(int i=3; i<=n; i++)
	{
		if( directie(st[vf-1], st[vf], i) > 0 )
			push(i);
		else
		{
			while( directie(st[vf-1], st[vf], i) <= 0  && vf>=1)
				pop();
			 push(i);
		}
	}
}

int main()
{
	citire();
	solve();
	afisare();
	return 0;
}