Cod sursa(job #885455)

Utilizator antonioteoZait Teodor Antonio antonioteo Data 21 februarie 2013 23:43:37
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.3 kb
#include <cstdio>
#include <algorithm>
#include <cmath>
#define max_N 120004
#define dd pair <double,double>
#define x first
#define y second
using namespace std;
const char iname[] = "infasuratoare.in";
const char oname[] = "infasuratoare.out";
int N, i, j, head, pos;
dd v[max_N], stiva[max_N];
inline double detSemn(const dd &A, const dd &B, const dd &C)
{
	double p1 = A.x * (-1); double p2 = A.y * (-1);
	double a = p1 + B.x; double b = p2 + B.y;
	double c = p1 + C.x; double d = p2 + C.y;
	return (a * d - (b * c));
}
struct cmp
{
	bool operator() (const dd &pc1, const dd &pc2) const
	{
		if (detSemn(v[1], pc1, pc2) < 0) return 1;
		return 0;
	};
};
int main()
{
	freopen(iname,"r",stdin);
	freopen(oname,"w",stdout);
	scanf ("%d", &N);
	for (i = 1; i <= N; ++i)
		scanf("%lf%lf", &v[i].x, &v[i].y);
	pos = 1;
    for (i = 2; i <= N; ++i)
        if (v[i] < v[pos])
            pos = i;
    swap(v[1], v[pos]);
    sort(v + 2, v + N + 1, cmp());	
	stiva[1] = v[1];
	stiva[2] = v[2];
	head = 2;
	for (i = 3; i <= N; ++i)
	{
		while (head >= 2 && detSemn(stiva[head - 1], stiva[head], v[i]) > 0)
			--head;
		stiva[++head] = v[i];
	}
	printf("%d\n", head);
	for (i = head; i >= 1; --i)
	{
		printf ("%lf %lf", stiva[i].x, stiva[i].y);
		printf ("\n");
	}
	return 0;
}