Cod sursa(job #846175)

Utilizator enedumitruene dumitru enedumitru Data 1 ianuarie 2013 16:47:51
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.42 kb
// Infasuratoarea convexa prgram de 100 puncte. (Alg lui Hull).
#include <cstdio>
#include <algorithm>
#define Nmax 120005
#define EPS 1e-12
#define PDD pair<double, double>
#define x first
#define y second
using namespace std;
int N,H;
PDD v[Nmax], P[Nmax];
int st[Nmax], uz[Nmax];
void cit()
{	freopen("infasuratoare.in","r",stdin);
	scanf("%ld",&N);
	for(int i=1; i<=N; ++i) scanf("%lf %lf",&v[i].x, &v[i].y);
}
void afis()
{	freopen("infasuratoare.out","w",stdout);
	printf("%d\n", H);
    for (int i = 1; i <= H; ++i) printf("%.6lf %.6lf\n", P[i].x, P[i].y);
}
inline int cmp(double a, double b)
{   if (a + EPS < b) return -1;
    if (b + EPS < a) return +1;
    return 0;
}
int cmpHull(const PDD &a, const PDD &b)
{   int r = cmp(a.x, b.x);
    if (r != 0) return r == -1;
    return cmp(a.y, b.y) == -1;
}
int semn(PDD a, PDD b, PDD c)
{   double A = a.y-b.y, B = b.x-a.x, C = a.x*b.y - b.x*a.y;
    return cmp(A * c.x + B * c.y + C, 0);
}
void ConvexHull()
{	int i, k, pas = 1;
	sort(v+1, v+N+1, cmpHull);
	uz[2]=1; st[1]=1; st[2]=2; k=2; i=3;
	while (!uz[1])
    {   while (uz[i])
        {   if(i == N) pas = -1;
            i += pas;
        }
        while (k >= 2 && semn(v[st[k-1]], v[st[k]], v[i]) == -1) uz[st[k--]] = 0;
        st[++k] = i; uz[i] = 1;
    }
	H=k-1;
    for(i=1; i<=H; ++i) P[i]=v[st[i]];
    P[H+1]=P[1];
}
int main()
{	cit(); ConvexHull(); afis(); return 0;}