Cod sursa(job #538532)

Utilizator tudorsTudor Siminic tudors Data 21 februarie 2011 17:25:25
Problema Infasuratoare convexa Scor 80
Compilator cpp Status done
Runda Arhiva educationala Marime 1.31 kb
#include <stdio.h>
#include <algorithm>
#define N 120001
using namespace std;

typedef struct {double x,y;} PUNCT;
long long n,i,s,p;
PUNCT A[N],S[N],P[N];
FILE *f,*g;

bool operator < (const PUNCT &a, const PUNCT &b)
{
	if (a.y<b.y)
		return 1;
	else if (a.y==b.y)
		if (a.x<b.x)
			return 1;
	return 0;
}

int stanga(PUNCT a, PUNCT b, PUNCT c)
{
	float st;
	st=a.x*b.y+b.x*c.y+c.x*a.y-a.y*b.x-b.y*c.x-a.x*c.y;
	if (st>0)
		return 1;
	else
		return 0;
}

int main()
{
	f=fopen("infasuratoare.in","r");
	g=fopen("infasuratoare.out","w");
	
	fscanf(f,"%lld",&n);
	for (i=1;i<=n;++i)
		fscanf(f,"%lf %lf",&A[i].x,&A[i].y);
	sort(A+1,A+n+1);
	s=2;
	S[1]=A[1];
	S[2]=A[2];
	i=3;
	while (i<=n)
		if (stanga(S[s-1],S[s],A[i]))
		{
			S[++s]=A[i];
			i++;
		}
		else
		{
			s--;
			if (s<2)
			{
				S[++s]=A[i];
				i++;
			}
		}
	P[1]=A[n];
	P[2]=A[n-1];
	p=2;
	i=n-2;
	while (i>=1)
	{
		if (stanga(P[p-1],P[p],A[i]))
		{
			P[++p]=A[i];
			i--;
		}
		else
		{
			p--;
			if (p<2)
			{
				P[++p]=A[i];
				p--;
			}
		}
	}
	if (n==3)
		fprintf(g,"%d\n",3);
	else
		fprintf(g,"%lld\n",s+p-2);
	for (i=1;i<=s;++i)
		fprintf(g,"%.6lf %.6lf\n",S[i].x,S[i].y);
	for (i=2;i<p;++i)
		fprintf(g,"%.6lf %.6lf\n",P[i].x,P[i].y);
	fclose(f);
	fclose(g);
	return 0;
}