Cod sursa(job #709427)

Utilizator roots4Irimia Alexandru Gabriel roots4 Data 8 martie 2012 09:04:59
Problema Infasuratoare convexa Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.17 kb
#include<stdio.h>
#include<algorithm>
#define val 120010
using namespace std;
int i , n , punct_initial,D[val],u;
float x_min,y_min;
struct coordonate{
	float x;
	float y;
}S[val];

const char InFile[]="infasuratoare.in";
const char OutFile[]="infasuratoare.out";

FILE*f=fopen(InFile,"r");
FILE*g=fopen(OutFile,"w");

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

float 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))/2;
}

int main(){
	
	fscanf(f,"%d",&n);
	
	for(i=1;i<=n;i++)
		fscanf(f,"%f %f",&S[i].x,&S[i].y);
	punct_initial=1;
	for(i=1;i<=n;i++){
		if(i==punct_initial)
			continue;
		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;
	}
	
	sort(S+1,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,"%f %f\n",S[D[i]].x+x_min,S[D[i]].y+y_min);
	
	return 0;
}