Cod sursa(job #363668)

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

using namespace std;

const int MAXN = 120000;
const int INF = 1000000000;

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

double x[MAXN],y[MAXN];
long double V[MAXN];
int pi,IND[MAXN],N,stiva[MAXN];

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

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]);
}

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];
}