Cod sursa(job #719112)

Utilizator maritimCristian Lambru maritim Data 21 martie 2012 14:31:58
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.25 kb
#include<stdio.h>
#include<algorithm>
using namespace std;

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

typedef struct
{
	double x,y;
} xy;

#define MaxN 120010

int N,nr = 2;
xy A[MaxN],S[MaxN];

void citire(void)
{
	fscanf(f,"%d ",&N);
	for(int i=1;i<=N;i++)
		fscanf(f,"%lf %lf",&A[i].x,&A[i].y);
}

inline int FirstPoint(void)
{
	int P = 1;
	
	for(int i=2;i<=N;i++)
		if(A[i].y < A[P].y || (A[i].y == A[P].y && A[i].x < A[P].x))
			P = i;
		
	return P;
}

inline void Swap(int a,int b)
{
	xy aux = A[a];
	A[a] = A[b];
	A[b] = aux;
}

inline int cmp(xy a,xy b)
{
	return (a.x-A[1].x)/(a.y-A[1].y) > (b.x-A[1].x)/(b.y-A[1].y);
}

inline int IntoarcereDreapta(xy p0,xy p1,xy p2)
{
	if(1LL*(p2.x-p0.x)*(p1.y-p0.y)-1LL*(p1.x-p0.x)*(p2.y-p0.y) < 0)
		return 1;
	
	return 0;
}

void Rezolvare(void)
{
	Swap(1,FirstPoint());
	
	sort(A+2,A+N+1,cmp);
	
	S[1] = A[1];
	S[2] = A[2];
	
	for(int i=3;i<=N;i++)
	{
		while(!IntoarcereDreapta(S[nr-1],S[nr],A[i]))
			-- nr;
		
		S[++nr] = A[i];
	}
}

void Afisare(void)
{
	fprintf(g,"%d\n",nr);
	
	for(int i=1;i<=nr;i++)
		fprintf(g,"%.6lf %.6lf\n",S[i].x,S[i].y);
}

int main()
{
	citire();
	Rezolvare();
	Afisare();
}