Cod sursa(job #847051)

Utilizator Bogdan_tmmTirca Bogdan Bogdan_tmm Data 3 ianuarie 2013 11:06:47
Problema Infasuratoare convexa Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.3 kb
#include <algorithm>
#include <vector>
#include <stack>

using namespace std;
#define N_MAX 120002
#define ld long double
#define x first
#define y second

typedef pair <double, double> p;

p a[N_MAX];
int n;

vector <int> st;

int pivot = 0;
struct cmp{
	bool operator () (const p &i, const p &j) const{
		return (ld) (j.x - a[pivot].x) * (i.y - a[pivot].y) < (ld) (j.y - a[pivot].y) * (i.x - a[pivot].x);
	}
};

inline ld sign(const int &i, const int &j, const int &k){
	return (ld) (a[k].x - a[i].x) * (a[j].y - a[i].y) - (ld) (a[k].y - a[i].y) * (a[j].x - a[i].x);
}

int main(){
	freopen("infasuratoare.in", "r", stdin);
	freopen("infasuratoare.out", "w", stdout);
	
	scanf("%d", &n);
	for(int i = 0; i < n; i ++){
		scanf("%lf %lf", &a[i].x, &a[i].y);
	}
	
	for(int i = 0; i < n; i ++){
		if(a[i].x < a[pivot].x || a[i].x == a[pivot].x && a[i].y < a[pivot].y){
			pivot = i;
		}
	}
	
	swap(a[pivot], a[0]);
	pivot = 0;
	
	sort(a + 1, a + n, cmp());
	
	st.push_back(pivot);
	for(int i = 1; i < n; i ++){
		if(st.size() > 1 && sign(st[st.size() - 2], st[st.size() - 1], i) > 0){
			st.pop_back();
		}
		st.push_back(i);
	}
	printf("%d\n", st.size());
	for(int i = 0; i < (int) st.size(); i ++){
		printf("%lf %lf\n", a[ st[i] ].x, a[ st[i] ].y);
	}
	return 0;
}