Cod sursa(job #701139)

Utilizator blustudioPaul Herman blustudio Data 1 martie 2012 13:52:07
Problema Infasuratoare convexa Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.21 kb
#include <cstdio>
#include <algorithm>
#include <vector>
using namespace std;

int n, pi;
double x[120001], y[120001];
vector<int> puncte;
int stack[120001], stack_size;

inline void stack_push(int x)
{
	stack_size++;
	stack[stack_size] = x;
}
double arie2(int a, int b, int c)
{
	return (double)(x[a] * y[b] + y[a] * x[c] + x[b] * y[c] - y[b] * x[c] - y[a] * x[b] - y[c] * x[a]);
}
bool unghi(int a, int b)
{
	return (double)(x[a] - x[pi]) * (y[a] - y[pi]) < (double)(x[b] - x[pi]) * (y[b] - y[pi]);
}
int main()
{
	freopen("infasuratoare.in", "r", stdin);
	freopen("infasuratoare.out", "w", stdout);
	scanf("%d", &n);
	pi = 0;
	x[0] = 1000000001;
	y[0] = 1000000001;
	for (int i = 1; i <= n; i++)
	{
		scanf("%lf %lf", &x[i], &y[i]);
		if ((x[i] < x[pi]) || ((x[i] == x[pi]) && (y[i] < y[pi])))
			pi = i;
	}
	for (int i = 1; i <= n; i++)
		if (i != pi)
			puncte.push_back(i);
	sort(puncte.begin(), puncte.end(), unghi);
	stack_push(pi);
	for (int i = 0; i < puncte.size(); i++)
	{
		if ((stack_size >= 2) && (arie2(stack[stack_size - 1], stack[stack_size], puncte[i]) > 0))
			stack_size--;
		stack_push(puncte[i]);
	}
	printf("%d\n", stack_size);
	for (int i = 1; i <= stack_size; i++)
		printf("%lf %lf\n", x[stack[i]], y[stack[i]]);
}