Cod sursa(job #268527)

Utilizator yoyolichIoana Ardeleanu yoyolich Data 1 martie 2009 13:15:58
Problema Infasuratoare convexa Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.2 kb
#include<stdio.h>
#include<stdlib.h>

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

struct punct { double x,y;} a[nmax],pst;
int n,i;
inline int isleft(punct p1, punct p2, punct p3)
{
	int left=((p2.x-p1.x)*(p3.y-p1.y)-(p3.x-p1.x)*(p2.y-p1.y));
	
	return left;
}

inline int cmp(punct *p1, punct *p2)
{
	int left=isleft(pst,*p1,*p2);
	if(left>0) return -1;
	if(left==0) return 0;
	if(left<0) return 1;
}

int main()
{
	fscanf(f,"%d",&n);
	for(i=1;i<=n;i++)
		fscanf(f,"%lf %lf",&a[i].x, &a[i].y);
	
	pst=a[1];
	int poz=1;
	
	for(i=2;i<=n;i++)
		if(a[i].y<pst.y) pst=a[i],poz=i;
		else
			if(a[i].y==pst.y)
				if(a[i].x<pst.x) pst=a[i],poz=i;
	
	punct aux;
	aux=a[1];
	a[1]=a[poz]; 
	a[poz]=aux;
	
	qsort(a+2,n-1,sizeof(punct), (int (*)(const void *, const void *))cmp);
	
	punct stiva[nmax];
	int k;
	stiva[++k]=a[1];
	for(i=2;i<=n;i++)
	{
		while(k>1 && isleft(stiva[k-1],stiva[k],a[i])<0) k--;
		stiva[++k]=a[i];
	}
	while (k > 1 && isleft(stiva[k],stiva[k],a[1])<0) k--;   
	fprintf(g,"%d\n",k);
	for(i=1;i<=k;i++) fprintf(g,"%.6lf %.6lf\n",stiva[i].x,stiva[i].y);
	
	fclose(f);
	fclose(g);
	return 0;
}