Cod sursa(job #1557938)

Utilizator Corneliu10Dumitru Corneliu Corneliu10 Data 28 decembrie 2015 14:37:11
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.22 kb
#include <cstdio>
#include <algorithm>
#define Nmax 120045

#define x first
#define y second

using namespace std;

typedef pair <double, double> Point;
Point v[Nmax];
Point st[Nmax];
int n,head;

double cross(Point A,Point B,Point C)
{
    return (C.y - A.y) * (B.x - A.x) - (C.x - A.x) * (B.y - A.y);
}

bool cmp(Point A,Point B)
{
    return cross(v[1], A, B) < 0;
}

void convex_hull()
{
    int i;
    st[1] = v[1];
    st[2] = v[2];
    head = 2;

    for(i = 3;i<=n;i++)
    {
        while(head >= 2 && cross(st[head - 1], st[head] , v[i]) > 0)
            head--;
        st[++head] = v[i];
    }
}

int main()
{
    int pos = 1,i;
    Point p;
    double x,y;
    freopen("infasuratoare.in","r",stdin);
    freopen("infasuratoare.out","w",stdout);

    scanf("%d",&n);
    for(i = 1;i<=n;i++)
    {
        scanf("%lf%lf",&v[i].x,&v[i].y);
        if(v[i].y < v[pos].y || (v[i].y == v[pos].y && v[i].x < v[pos].y))
            pos = i;
    }

    swap(v[1],v[pos]);
    sort(v + 2, v + n + 1, cmp);

    convex_hull();

    printf("%d\n",head);
    printf("%.9lf %.9lf\n",st[1].x,st[1].y);
    for(i = head ;i >= 2;i--)
        printf("%.9lf %.9lf\n",st[i].x,st[i].y);
}