Cod sursa(job #891572)

Utilizator noruIlies Norbert noru Data 25 februarie 2013 17:55:21
Problema Infasuratoare convexa Scor 20
Compilator cpp Status done
Runda Arhiva educationala Marime 0.97 kb
#include<stdio.h>
#include<algorithm>
using namespace std;
FILE *f=fopen("infasuratoare.in","r");
FILE *g=fopen("infasuratoare.out","w");
int n,vf;
typedef struct {double x,y;}NOD;
NOD st[12005],p[12005];
void citire()
{
	fscanf (f,"%d", &n);
    for (int i = 1; i <= n; ++i)
        fscanf (f,"%lf%lf", &p[i].x, &p[i].y);
}
bool cmp (NOD a, NOD b)
{
    return ((a.y < b.y) || (a.y == b.y && a.x < b.x));
}
float det(NOD a, NOD b, NOD c)
{
	return (b.x-a.x)*(c.y-a.y)-(b.y-a.y)*(c.x-a.x);
}
void convex_hull()
{
	sort(p+1,p+n+1,cmp);
	st[1]=p[1];
	st[2]=p[2];
	vf=2;
	int i;
	for (i=3;i<=n;i++)
	{	while (det(st[vf-1],st[vf],p[i])>0)
			vf--;
		st[++vf]=p[i];
	}
	for (i=n-1;i>=1;i--)
	{
		while (det(st[vf-1],st[vf],p[i])>0)
			vf--;
		st[++vf]=p[i];
	}
}
void afis()
{
	for (int i = vf; i >= 2; --i)
		fprintf (g,"%.12lf %.12lf\n", st[i].x, st[i].y);
}
int main()
{
	citire();
	convex_hull();
	fprintf(g,"%d\n",vf-1);
	afis();
	return 0;
}