Cod sursa(job #363709)

Utilizator coderumascatcoderu mascat coderumascat Data 14 noiembrie 2009 12:13:36
Problema Infasuratoare convexa Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.07 kb
#include <fstream>
#include <algorithm>
#define MAX 120010
using namespace std;
ifstream fi("infasuratoare.in");
ofstream fo("infasuratoare.out");
int N;
double X[MAX],Y[MAX];
int PI;
int ind[MAX],st[MAX];

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

long long semn(int i1,int i2,int i3){
	return (long double)X[i1] * Y[i2] + X[i2] * Y[i3] + X[i3] * Y[i1] - Y[i1] * X[i2] - Y[i2] * X[i3] - Y[i3] * X[i1];
}

int main(){
	fi>>N;
	X[0]=Y[0]=1000000001;
	PI=0;
	for (int i=1;i<=N;++i){
		fi>>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) ind[++ind[0]]=i;
	sort(ind+1,ind+ind[0]+1,cmp);
	st[st[0]=1]=PI;
	for (int i=1;i<=ind[0];++i) if (ind[i]!=PI){
		while (st[0]>=2 && semn(st[st[0]-1],st[st[0]],ind[i])>0) --st[0];
		st[++st[0]]=ind[i];
	}
	fo<<(N-st[0])<<"\n";
	st[++st[0]]=PI;
	reverse(st+1,st+st[0]+1);
	for (int i=1;i<st[0];++i){
		fo<<X[st[i]]<<" "<<Y[st[i]]<<"\n";
	}
	fi.close();fo.close();
		
	return 0;
}