Cod sursa(job #434852)

Utilizator s_holmesSherlock Holmes s_holmes Data 6 aprilie 2010 17:32:09
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.22 kb
#include <cstdio>
#include <algorithm>
using namespace std;
#define MAXN 120005
int N;
double X[MAXN], Y[MAXN];
int ind[MAXN];
int ST[MAXN];
int PCT = 1;

void citire()
{
	scanf("%d",&N);
	for(int i = 1 ; i <= N ; i++)
	{
		scanf("%lf%lf", &X[i], &Y[i]);
		if(X[i] < X[PCT] || (X[i] == X[PCT] && Y[i] < Y[PCT]))
			PCT = i;
		ind[i] = i;
	}
	swap(X[1], X[PCT]);
	swap(Y[1], Y[PCT]);
	PCT = 1;
}

bool cmp(int i,int j)
{
	return (X[i] - X[PCT]) * (Y[j] - Y[PCT]) > (X[j] - X[PCT]) * (Y[i] - Y[PCT]);
}

double prod(int i1,int i2,int i3)
{
	//negativ daca se afla in dreapta dreptei suport
	return (X[i2] - X[i1]) * (Y[i3] - Y[i1]) - (X[i3] - X[i1]) * (Y[i2] - Y[i1]);
}

void stiva()
{
	ST[++ST[0]] = PCT;
	ST[++ST[0]] = ind[2];
	for(int i = 3 ; i <= N ; i++)
	{
		while(ST[0] >= 1 && prod(ST[ST[0] - 1], ST[ST[0]], ind[i]) < 0)// pt coliniaritate <=
			ST[0]--;
		ST[++ST[0]] = ind[i];
	}
}

void scrie()
{
	printf("%d\n",ST[0]);
	for(int i = 1 ; i <= ST[0] ; i++)
		printf("%lf %lf\n", X[ST[i]], Y[ST[i]]);
}

int main()
{
	freopen("infasuratoare.in","r",stdin);
	freopen("infasuratoare.out","w",stdout);
	citire();
	sort(ind + 2, ind + N + 1, cmp);
	stiva();
	scrie();
	return 0;
}