Cod sursa(job #884997)

Utilizator antonioteoZait Teodor Antonio antonioteo Data 21 februarie 2013 15:54:26
Problema Infasuratoare convexa Scor 90
Compilator cpp Status done
Runda Arhiva educationala Marime 1.25 kb
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <algorithm>
#define nmax 120010
#define x first
#define y second
#define dd pair<double, double>
using namespace std;
const char iname[] = "infasuratoare.in";
const char oname[] = "infasuratoare.out";
dd A[nmax], st[nmax];
int r, N, i;
struct cmp
{
	bool operator () (const dd &A, const dd &B) const
	{
		if(A.y < B.y) return 1;
		if(A.y > B.y) return 0;
		if(A.x < B.x) return 1;
		return 0;
	};
};
inline int semnDet(dd a, dd b, dd c)
{
    double det_abc = (a.x * b.y + a.y * c.x + b.x * c.y - b.y * c.x - c.y * a.x - b.x * a.y);
    return (det_abc) < 0;
}
void ConvexHull()
{
	st[++r] = A[1];
	st[++r] = A[2];
	for(i = 3; i <= N; ++i)
	{
		while(r >= 2 && semnDet(st[r - 1], st[r], A[i])) 
			--r;
		st[++r] = A[i];
	}
	for(i = N - 1; i; --i)
	{
		while(r >= 2 && semnDet(st[r - 1], st[r], A[i]))
			--r;
		st[++r] = A[i];
	}
	--r;
	printf("%d\n", r);
	for(i = 1; i <= r; ++i) printf("%lf %lf\n", st[i].x, st[i].y);
}
int main()
{
    freopen(iname, "r", stdin);
    freopen(oname, "w", stdout);
    scanf("%d", &N);
    for(i = 1; i <= N; ++i) scanf("%lf %lf", &A[i].x, &A[i].y);
    sort(A + 1, A + N + 1, cmp());
    ConvexHull();
    return 0;
}