Cod sursa(job #1922892)

Utilizator Corneliu10Dumitru Corneliu Corneliu10 Data 10 martie 2017 19:26:50
Problema Infasuratoare convexa Scor 20
Compilator cpp Status done
Runda Arhiva educationala Marime 1.25 kb
#include <vector>
#include <cstdio>
#include <algorithm>
#include <cmath>
#define NMAX 120010

#define x first
#define y second

using namespace std;

typedef pair<double, double> punct;

punct v[NMAX],st[NMAX];
int n,head;

int cross_product(punct A,punct B,punct C)
{
    return (C.y - A.y)*(B.x - A.x) - (B.y - A.y)*(C.x - A.x);
}

int cmp(punct p1,punct p2)
{
    return cross_product(v[1],p1,p2) < 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_product(st[head-1],st[head],v[i]) > 0)
            head--;
        st[++head] = v[i];
    }
}

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

    scanf("%d",&n);

    pos = 1;
    for(i=1;i<=n;i++)
    {
        scanf("%lf%lf",&x,&y);

        v[i].x = x;
        v[i].y = y;
        if(v[i].y < v[pos].y || (v[i].y==v[pos].y && v[i].x < v[i].y))
            pos = i;
    }

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

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