Cod sursa(job #1459852)

Utilizator al.mocanuAlexandru Mocanu al.mocanu Data 10 iulie 2015 23:37:46
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.99 kb
#include <stdio.h>
#include <algorithm>
#include <vector>
#define MAX 120005
using namespace std;

typedef struct{
	double x, y;
} Punct;

int n, m, i, best;
Punct p[MAX], stack[MAX];

double ccw(const Punct& p1, const Punct& p2, const Punct& p3){
	return (p2.x - p1.x) * (p3.y - p1.y) - (p2.y - p1.y) * (p3.x - p1.x);
}

int compare(const Punct& r, const Punct& q){
	return ccw(p[0], r, q) < 0;
}

int main(){
	freopen("infasuratoare.in", "r", stdin);
	freopen("infasuratoare.out", "w", stdout);
	scanf("%d", &n);
	for(i = 0; i < n; i++){
		scanf("%lf%lf", &p[i].x, &p[i].y);
		if(p[best].y > p[i].y)
			best = i;
		else if(p[best].y == p[i].y)
			if(p[best].x > p[i].x)
				best = i;
	}
	swap(p[0], p[best]);
	sort(p + 1, p + n, compare);

	m = 1;
	stack[0] = p[0];
	stack[1] = p[1];
	for(i = 2; i < n; i++){
		while(m >= 1 && ccw(stack[m - 1], stack[m], p[i]) > 0)
			m--;
		stack[++m] = p[i];
	}

	printf("%d\n", m + 1);
	for(i = m; i >= 0; i--)
		printf("%lf %lf\n", stack[i].x, stack[i].y);
	return 0;
}