Cod sursa(job #381915)

Utilizator titusuTitus C titusu Data 12 ianuarie 2010 00:31:10
Problema Infasuratoare convexa Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.74 kb
using namespace std;
#include <cstdio>
#include <algorithm>
#define NN 120005
struct Punct{
	double x,y;
};



Punct P[NN], pStart;
int n, Poz[NN], Stack[NN], nS,istart;

bool pcmp(int i, int j){
	//panta lui P[i] < panta lui P[j]
	double x1=P[i].x-P[istart].x, y1=P[i].y-P[istart].y, x2=P[j].x-P[istart].x, y2=P[j].y-P[istart].y;
	if(y1*x2<x1*y2)
		return true;
	if(y1*x2>x1*y2)
		return false;
	return x1*x1+y1*y1<x2*x2+y2*y2;
}

void Afis(int v[], int n){
	for(int i=1;i<=n;++i)
		printf("(%.1lf %.1lf) ",P[v[i]].x, P[v[i]].y);
	printf("\n");
}

void Push(int i){	Stack[++nS]=i;	}
void Pop(){	--nS;	}
int Directie(int i,int j, int k){
	//directia segmentului P[j]P[k] fata de P[i]P[j]
	//   <0 dreapta , =0  inainte , >0 stanga
	long double xi=P[i].x, yi=P[i].y, xj=P[j].x, yj=P[j].y, xk=P[i].x, yk=P[k].y;
	long double A=(xj-xi)*(yk-yi)-(xk-xi)*(yj-yi);
	if(A<0)
		return -1;
	if(A==0)
		return 0;
	return 1;
}

int main(){
	freopen("infasuratoare.in","r",stdin);
	scanf("%d",&n);
	for(int i=1;i<=n;++i)
		scanf("%lf%lf", &P[i].x, &P[i].y);
	istart=1;
	for(int i=2;i<=n;++i)
		if(P[i].x<P[istart].x)
			istart=i;
		else
			if(P[i].x==P[istart].x && P[i].y<P[istart].y)
				istart=i;
	//printf("(%.1lf %.1lf)\n",P[istart].x, P[istart].y);
	for(int i=1;i<=n;++i)
		if(i!=istart)
			Poz[++Poz[0]]=i;
	//Afis(Poz,Poz[0]);
	sort(Poz+1, Poz+Poz[0]+1,pcmp);
	//Afis(Poz,Poz[0]);
	nS=0;
	Push(istart);
	Push(Poz[1]);
	for(int i=2;i<=Poz[0];++i){
		int d=Directie(Stack[nS-1],Stack[nS], Poz[i]);
		if(d>=0)
			Push(Poz[i]);
		else{
			while(d<0 && nS>2){
				Pop();
				d=Directie(Stack[nS-1],Stack[nS], Poz[i]);
			}
			Push(Poz[i]);
		}
	}
	freopen("infasuratoare.out","w",stdout);
	printf("%d\n",nS);
	for(int i=1;i<=nS;++i)
		printf("%.6lf %.6lf\n",P[Stack[i]].x, P[Stack[i]].y);
}