Cod sursa(job #1922940)

Utilizator Corneliu10Dumitru Corneliu Corneliu10 Data 10 martie 2017 19:43:20
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.39 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;

double 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 j,i,pos,m;
    double x,y;
    freopen("infasuratoare.in","r",stdin);
    freopen("infasuratoare.out","w",stdout);

    scanf("%d",&m);

    pos = 1;
    n=1;
    for(i=1;i<=m;i++)
    {
        scanf("%lf%lf",&x,&y);
        for(j=i-1;j>=1;j--)
            if(x==v[i].x && y==v[i].y)
                break;

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

        n++;
    }
    n--;

    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);
}