Cod sursa(job #709429)

Utilizator roots4Irimia Alexandru Gabriel roots4 Data 8 martie 2012 09:05:23
Problema Infasuratoare convexa Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.04 kb
#include<stdio.h>
#include<algorithm>
using namespace std;
int i , q , S[120010],n,minim,u;
float x_min,y_min;
float d;
struct pereche{
	float x;
	float y;
}V[120010];

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

void read(){
	fscanf(f,"%d",&n);
	for(i=1;i<=n;i++)
		fscanf(f,"%f%f",&V[i].x,&V[i].y);
}

int cmp(pereche a, pereche b){
	if(a.x*b.y<a.y*b.x)
		return 0;
	return 1;
}

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

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