Cod sursa(job #709572)

Utilizator roots4Irimia Alexandru Gabriel roots4 Data 8 martie 2012 11:49:31
Problema Infasuratoare convexa Scor 20
Compilator cpp Status done
Runda Arhiva educationala Marime 1.13 kb
#include<stdio.h>
#include<algorithm>
#define val 120300
using namespace std;
int i , n , punct_initial,D[val],u;
double x_min,y_min;
struct coordonate{
	double x;
	double y;
}S[val],aux;

FILE*f=fopen("infasuratoare.in","r");
FILE*g=fopen("infasuratoare.out","w");

int cmp(coordonate a, coordonate b){
	return a.y*b.x<b.y*a.x;
}

int unghi(int a , int b , int c){
	return (S[a].x*(S[b].y-S[c].y)+S[b].x*(S[c].y-S[a].y)+S[c].x*(S[a].y-S[b].y));
}

int main(){
	
	fscanf(f,"%d",&n);
	
	for(i=1;i<=n;i++)
		fscanf(f,"%lf %lf",&S[i].x,&S[i].y);
	punct_initial=1;
	for(i=1;i<=n;i++)
		if((S[i].y<S[punct_initial].y)||(S[i].y==S[punct_initial].y&&S[i].x<S[punct_initial].x))
			punct_initial=i;
	
	x_min=S[punct_initial].x;
	y_min=S[punct_initial].y;
	
	for(i=1;i<=n;i++){
		S[i].x-=x_min;
		S[i].y-=y_min;
	}
	aux=S[1];
	S[1]=S[punct_initial];
	S[punct_initial]=aux;
	sort(S+2,S+n+1,cmp);
	
	D[1]=1;D[2]=2;u=2;
	for(i=3;i<=n;i++){
		while(unghi(D[u-1],D[u],i)<0)
			u--;
		D[++u]=i;
	}
	
	fprintf(g,"%d\n",u);
	
	for(i=1;i<=u;i++)
		fprintf(g,"%lf %lf\n",S[D[i]].x+x_min,S[D[i]].y+y_min);
	
	return 0;
}