Cod sursa(job #383967)

Utilizator loginLogin Iustin Anca login Data 18 ianuarie 2010 20:42:24
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.35 kb
using namespace std;
#include <cstdio>
#include <algorithm>
#define NN 120005

struct punct{
	double x,y;
};
int n, nS;
punct v[NN], S[NN];

void citire(){
	freopen("infasuratoare.in","r",stdin);
	scanf("%d", &n);
	for(int i=0;i<n;i++)
		scanf("%lf%lf", &v[i].x, & v[i].y);
}

void primulPunct(){
	int poz=0;
	for(int i=1;i<n;++i)
		if(v[i].x<v[poz].x)
			poz = i;
		else
			if(v[i].x==v[poz].x && v[i].y<v[poz].y) 
				poz = i;
	punct aux=v[0];v[0]=v[poz];v[poz]=aux;
}

void afisare(punct a[], int n,int dep=0){
	for(int i=dep;i<n+dep;++i)
		printf("%.6lf %.6lf\n",a[i].x,a[i].y);
}

int directie(punct A, punct B, punct C){
	double d=(B.x-A.x)*(C.y-A.y)-(C.x-A.x)*(B.y-A.y);
	if(d==0)
		return 0; //inainte
	if(d<0)
		return -1; //dreapta
	return 1;//stanga
}

int fcmp(punct A, punct B){
	if (directie(v[0],A,B)>0)
		return 1;
	if(directie(v[0],A,B)<0)
		return 0;
	return (v[0].x-A.x)*(v[0].x-A.x)+(v[0].y-A.y)*(v[0].y-A.y)
					<
			(v[0].x-B.x)*(v[0].x-B.x)+(v[0].y-B.y)*(v[0].y-B.y);
	
}

void sortare(){
	sort(v+1,v+n,fcmp);
}

void graham(){
	nS=0;
	S[++nS]=v[0];
	S[++nS]=v[1];
	for(int i=2;i<n;++i){
		while(directie(S[nS-1],S[nS],v[i])<=0 && nS>1)
			nS--;
		S[++nS]=v[i];
	}
}

int main(){
	citire();
	primulPunct();
	sortare();
	graham();
	//afisare(v,n);
	//printf("\n");
	freopen("infasuratoare.out","w",stdout);
	printf("%d\n",nS);
	afisare(S,nS,1);
	return 0;
}