Cod sursa(job #688836)

Utilizator balakraz94abcd efgh balakraz94 Data 23 februarie 2012 21:30:08
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.41 kb
#include<cstdio>
#include<algorithm>
#define infile "infasuratoare.in"
#define outfile "infasuratoare.out"
#define n_max 120005
#define INF 1<<30
using namespace std;

struct punct {
	double x, y; };

	
punct a[n_max];

int nxt[n_max], ST[n_max];

int N, P;


inline bool cmp( int i, int j)
{
	return (a[i].x - a[P].x) * (a[j].y - a[P].y) < (a[j].x - a[P].x) * (a[i].y - a[P].y);
}

inline double semn(int i1, int i2, int i3){
	return a[i1].x * a[i2].y + a[i3].x * a[i1].y + a[i2].x * a[i3].y - a[i3].x * a[i2].y - a[i2].x * a[i1].y - a[i1].x * a[i3].y; }

void citeste()
{
	freopen(infile, "r", stdin);
	
	scanf("%d",&N);
	
	for(int i=1; i<=N; ++i)
		scanf("%lf %lf",&a[i].x, &a[i].y);

	fclose(stdin);
}



void rezolva()
{		
	a[P].x = a[P].y = INF;
	
	for(int i=1; i<=N; ++i)
		if(a[i].x < a[P].x || (a[i].x == a[P].x && a[i].y < a[P].y))
			P = i;
	
	for(int i =1; i<=N; ++i)
		if(i != P)
			nxt[++nxt[0]] = i;
	
	sort(nxt+1, nxt + nxt[0] + 1, cmp);	
	
	ST[++ST[0]] = P;
	
	for(int i=1; i<=nxt[0]; ++i)
	{
		if(nxt[i] == P)
			continue;
		
		while(ST[0] >= 2 && semn(ST[ST[0]-1], ST[ST[0]], nxt[i]) > 0)
			ST[0]--;
		
		ST[++ST[0]] = nxt[i];
	}	
}



void afiseaza()
{
	freopen(outfile, "w", stdout);
	
	printf("%d\n", ST[0]);
	
	reverse(ST+1, ST + ST[0] + 1);
	
	for(int i = 1; i <= ST[0] ; ++i)
		printf("%lf %lf\n", a[ST[i]].x, a[ST[i]].y);
	
	fclose(stdout);
}



int main()
{
	citeste();
	
	rezolva();
	
	afiseaza();
	
	return 0;
}