Cod sursa(job #272408)

Utilizator the1dragonIonita Alexandru the1dragon Data 6 martie 2009 23:31:45
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.34 kb
#include<stdio.h>
#include<stdlib.h>
#define N_MAX 128000

struct point
{
	double x, y;
}  v[N_MAX];

int cmp(const void *A, const void*B)
{
	point *a, *b;
	a=(point *)A;
	b=(point *)B;
	if (a->x > b->x)
		return 1;
	if ((a->x == b->x) && (a->y > b->y ))
		return 1;
	return -1;
}

int q(int a, int b, int c)
{
	double det= v[c].x * (v[a].y-v[b].y) + v[c].y * (v[b].x-v[a].x) +v[a].x * v[b].y - v[b].x *v[a].y;
	if (det < 0) return 1;
	return 0;
}

int st[N_MAX], dr[N_MAX], stn, drn;
int main()
{
   freopen("infasuratoare.in", "r", stdin);
   freopen("infasuratoare.out", "w", stdout);
	//freopen("date.in", "r", stdin);
	//freopen("date.out", "w", stdout);
	int n, i;
	scanf("%d", &n);
	for (i=1;i<=n; i++)
		scanf("%lf %lf", &(v[i].x), &(v[i].y));
	qsort(&v[1], n, sizeof(point), cmp);

	st[1]=1;
	st[2]=2;
	dr[1]=1;
	dr[2]=2;
	stn=2;
	drn=2;
	for (i=3; i<=n; i++)
	{
		stn++;
		drn++;
		st[stn]=i;
		dr[drn]=i;
		while (q(st[stn-2], st[stn-1], st[stn])&& (stn>=3))
		{
			stn--;
			st[stn]=st[stn+1];
		}
		while((!q(dr[drn-2], dr[drn-1], dr[drn])) && (drn>=3))
		{
			drn--;
			dr[drn]=dr[drn+1];
		}
	}
	for (i=drn-1; i>1; i--)
	{
		++stn;
		st[stn]=dr[i];
	}
	printf("%d\n", stn);
	for (i=1; i<=stn; i++)
	{
		printf("%lf %lf\n", v[st[i]].x, v[st[i]].y);
	}
	fclose(stdout);
	return 0;

}