Cod sursa(job #413706)

Utilizator borsoszalanBorsos Zalan borsoszalan Data 8 martie 2010 23:16:13
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.15 kb
#include <cstdio>
#include <algorithm>
#include <vector>
using namespace std;

const int N_MAX = 120000;

int n;
double x[N_MAX], y[N_MAX];
int v[N_MAX];
int init;

bool ind_comp ( int a, int b ) {
	return (x[a] - x[init]) * (y[b] - y[init]) < (y[a] - y[init]) * (x[b] - x[init]);
}

long double semn ( int p1, int p2, int p3 ) {
	return (long double)x[p1]*y[p2] + (long double)x[p2]*y[p3] + x[p3]*y[p1] - (long double)y[p1]*x[p2] - (long double)y[p2]*x[p3] - (long double)y[p3]*x[p1];
}

int main() {
	freopen("infasuratoare.in","rt",stdin);
	freopen("infasuratoare.out","wt",stdout);
	scanf("%d",&n);
	init = 0;
	for (int i = 0; i < n; ++i) {
		scanf("%lf %lf",&x[i],&y[i]);
		if (x[i] < x[init] || x[i] == x[init] && y[i] < y[init]) init = i;
	}
	for (int i = 0, j = 0; i < n; ++i)
		if (i != init)
			v[j++] = i;
	sort(v,v+n-1,ind_comp);
	vector<int> st;
	st.push_back(init);
	for (int i = 0; i < n-1; ++i) {
		for (; st.size() > 1 && semn(st[st.size()-2], st[st.size()-1], v[i]) > 0; st.pop_back());
		st.push_back(v[i]);
	}
	reverse(st.begin(), st.end());
	printf("%d\n",st.size());
	for (int i = 0; i < st.size(); ++i) printf("%.6lf %.6lf\n",x[st[i]],y[st[i]]);
	return 0;
}