Cod sursa(job #363675)

Utilizator ada_sAda-Mihaela Solcan ada_s Data 14 noiembrie 2009 10:17:30
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.41 kb
#include <stdio.h>
#include <math.h>
#include <algorithm>

using namespace std;

const int NMAX=120000; ///////////////////////////10010
const int INF=1000000000;

bool comp(int i, int j);
long double semn(int i1, int i2, int i3);


double x[NMAX], y[NMAX];
int pctInit=0, i, pi, n, ind[NMAX], stiva[NMAX];

int main()
{
	freopen("infasuratoare.in", "r", stdin);  ///////////////////
	freopen("infasuratoare.out", "w", stdout);   ////////////////////
	scanf("%d", &n);
	x[0]=INF;
	y[0]=INF;
	for (i=1; i<=n; i++)
	{
		scanf("%lf %lf", &x[i], &y[i]);   //////////%ld
		if ((x[pctInit]>x[i])||((x[pctInit]==x[i])&&(y[pctInit]>y[i])))
			pctInit=i;
	}//for i
	for (i=1; i<=n; i++)
	{
		if (i!=pctInit)
			ind[++ind[0]]=i;
	}//for i
	pi=pctInit;
	sort(ind+1, ind+ind[0]+1, comp);
	stiva[0]=1;
	stiva[stiva[0]]=pctInit;
	for (i=1; i<=ind[0]; i++)
	{
		if (ind[i]!=pctInit)
			while ((semn(stiva[stiva[0]-1], stiva[stiva[0]], ind[i])>0)&&(stiva[0]>1))
				stiva[0]--;
		stiva[++stiva[0]]=ind[i];
	}//for i
	stiva[++stiva[0]]=pctInit;
	printf("%d\n",stiva[0]-1);
	reverse(stiva+1, stiva+stiva[0]+1);
	for (i=1;i<stiva[0]; i++)
		printf("%lf %lf\n",x[stiva[i]],y[stiva[i]]);
	return 0;
}//main

bool comp(int i, int j)
{
	return (double)(x[i]-x[pi])*(y[j]-y[pi]) < (double)(x[j]-x[pi])*(y[i]-y[pi]);
}//comp

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