Cod sursa(job #885435)

Utilizator Claudiu95Vartolomei Alexandru Claudiu Claudiu95 Data 21 februarie 2013 22:53:44
Problema Infasuratoare convexa Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 0.97 kb

#include<cstdio>	
#include<list>
#include<math.h>
#include<algorithm>
using namespace std;
const int maxn=120002;
const double oo = 1e-12;
int n,check[maxn],nre;
bool viz[maxn];
struct muchie{
	float x,y;
};
muchie v[maxn];
void citire(){
	int i;
	scanf("%d",&n);
	for(i=1;i<=n;++i){
		scanf("%f%f",&v[i].x,&v[i].y);
	}
}
int compare(muchie A,muchie B){
	return A.x<B.x || A.x<B.x && A.y<B.y;
}
double compara( muchie A, muchie B, muchie C){
	return (C.y-A.y)*(B.x-A.x)-(B.y-A.y)*(C.x-A.x);
}
int main(){
	freopen("infasuratoare.in","r",stdin);
	freopen("infasuratore.out","w",stdout);
	citire();
	sort(v+1,v+n+1,compare);
	check[1]=1;
	check[2]=2;
	nre=2;
	for(int i=3;i<n;++i){
		while(nre>2 && compara(v[nre-1],v[nre],v[i])<oo){
			
			--nre;
			
		}
		++nre;
		check[nre]=i;
	}
	printf("%d\n",nre+1);	
	for(int i=1;i<=nre;++i){
		printf("%lf %lf\n",v[check[i]].x,v[check[i]].y);
	}
	printf("%lf %lf",v[n].x,v[n].y);
	
	return 0;
}