Cod sursa(job #708325)

Utilizator GavrilaVladGavrila Vlad GavrilaVlad Data 6 martie 2012 18:36:35
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.18 kb
#include <cstdio>
#include <algorithm>

using namespace std;

#define maxn 120010

int n, k, a, b, st0, nd;
int st[maxn];
struct punct
{
    double x, y;
};
punct p[maxn];

inline int cmp(const punct &a, const punct &b)
{
	return (a.x-p[1].x)*(b.y-p[1].y)<(b.x-p[1].x)*(a.y-p[1].y);
}

inline int semn(const punct &a, const punct &b, const punct &c)
{
    double val = a.x*b.y + b.x*c.y + c.x*a.y - a.x*c.y - b.x*a.y - c.x*b.y;
    if(val>0)
        return 1;
    if(val<0)
        return -1;
    return 0;
}

void infasuratoare()
{
    for(int i=1; i<=nd; ++i)
        if(p[i].x<p[1].x || (p[i].x==p[1].x && p[i].y<p[1].y))
            swap(p[i], p[1]);

    sort(p+2, p+nd+1, cmp);
    for(int i=1; i<=nd; ++i)
    {
        if(st0>=2)
            while(st0>=2 && semn(p[st[st0-1]], p[st[st0]], p[i])>0)
                --st0;
        st[++st0]=i;
    }
}

int main()
{
    freopen("infasuratoare.in", "r", stdin);
    freopen("infasuratoare.out", "w", stdout);

    scanf("%d", &nd);
    for(int i=1; i<=nd; ++i)
        scanf("%lf%lf", &p[i].x, &p[i].y);

    infasuratoare();

    printf("%d\n", st0);
    for(int i=st0; i; --i)
        printf("%.6lf %.6lf\n", p[st[i]].x, p[st[i]].y);

    return 0;
}