Cod sursa(job #641694)

Utilizator sebii_cSebastian Claici sebii_c Data 29 noiembrie 2011 02:24:48
Problema Infasuratoare convexa Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.45 kb
#include <fstream>
#include <algorithm>
#include <vector>
#include <cstdio>
#include <cstring>
#include <math.h>

using namespace std;

const int NMAX = 120005;
const int INF = 0x3f3f3f3f;

double X[NMAX], Y[NMAX];
int primul, ind[NMAX], st[NMAX], n;

inline bool comp(int i, int j)
{
	return (double)(X[i] - X[primul]) * (Y[j] - Y[primul]) < (double)(X[j] - X[primul]) * (Y[i] * Y[primul]);
}

inline long double cross(int i, int j, int k)
{
	return (long double)X[i] * Y[j] + X[j] * Y[k] + X[k] * Y[i] - Y[i] * X[j] - Y[j] * X[k] - Y[k] * X[i];
}

int main()
{
	ifstream fin("infasuratoare.in");
	freopen("infasuratoare.out", "w", stdout);

	fin >> n;
	X[0] = INF, Y[0] = INF;
	int primul_point = 0;

	for (int i = 1; i <= n; ++i) {
		fin >> X[i] >> Y[i];
		if (X[i] < X[primul_point] || (X[i] == X[primul_point] && Y[i] < Y[primul_point]))
			primul_point = i;
	}

	primul = primul_point;
	for (int i = 1; i <= n; ++i) {
		if (i == primul_point)
			continue;
		ind[++ind[0]] = i;
	}
	
	sort(ind + 1, ind + ind[0] + 1, comp);
	st[++st[0]] = primul_point;
	
	for (int i = 1; i <= ind[0]; ++i) {
		if (ind[i] != primul_point)
		 	while (st[0] >= 2 && cross(st[st[0] - 1], st[st[0]], ind[i]) > 0)
				--st[0];
		st[++st[0]] = ind[i];
	}
	st[++st[0]] = primul_point;
	
	printf("%d\n", st[0] - 1);
	reverse(st + 1, st + st[0] + 1);
	for (int i = 1; i < st[0]; ++i) 
		printf("%lf %lf\n", X[st[i]], Y[st[i]]);
	return 0;
}