Cod sursa(job #2246034)

Utilizator akumariaPatrascanu Andra-Maria akumaria Data 26 septembrie 2018 14:40:31
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 2.46 kb
#include <cstdio>
#include <vector>
#include <cmath>

using namespace std;

double eps = pow(10, -12);

struct point
{
    double x, y;
};

point points[120002];

double ab(double x)
{
    if(x>0)
        return x;
    return 0-x;
}

double cross_product(const point &A, const point &B, const point &C)
{
    return (B.x - A.x) * (C.y - A.y) - (B.y - A.y) * (C.x - A.x);
}

int comp(const point &p1, const point &p2)
{
    double cp = cross_product(points[1], p1, p2);
    if (cp < 0)
        return -1;
    if (cp == 0)
        return 0;
    return 1;
}

bool eq(const double &x1, const double &x2)
{
    return ab(x1-x2) < eps;
}

bool operator ==(const point &p1, const point &p2)
{
   return eq(p1.x, p2.x) && eq(p1.y, p2.y);
}

void quicksort(int st, int dr)
{
    if(st >= dr)
        return;
    int i, j;
    point aux;

    i = st-1;
    for(j=st; j<dr; ++j)
        if (comp(points[j], points[dr]) > 0)
        {
            ++i;
            aux = points[i];
            points[i] = points[j];
            points[j] = aux;
        }

    aux = points[dr];
    points[dr] = points[i+1];
    points[i+1] = aux;
/*
    for(j=st; j<=dr; ++j)
    {
        if(j == i+1)
            printf("pivot ");
        printf("%f %f\n", points[j].x, points[j].y);
    }
    printf("\n");
*/
    quicksort(st, i);
    quicksort(i+2, dr);

}

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

    int n, i, min_ind = 1;
    point aux;

    scanf("%d", &n);

    for(i=1; i<=n; ++i)
    {
        scanf("%lf%lf", &points[i].x, &points[i].y);
        if (points[i].y < points[min_ind].y)
            min_ind = i;
        if (eq(points[i].y, points[min_ind].y) && points[i].x < points[min_ind].x)
            min_ind = i;
    }

    aux = points[min_ind];
    points[min_ind] = points[1];
    points[1] = aux;

    quicksort(2, n);
    points[n+1] = points[1];
/*
    for(i=1; i<=n; ++i)
        printf("%f %f\n", points[i].x, points[i].y);
    printf("\n");
*/
    point st[n+1];
    st[1] = points[1];
    st[2] = points[2];
    min_ind = 2;

    for(i=3; i<=n; ++i)
    {
        while(min_ind >=2 &&  cross_product(st[min_ind-1], st[min_ind], points[i]) < 0)
            --min_ind;
        st[++min_ind] = points[i];
    }

    printf("%d\n", min_ind);
    for(i=1; i<=min_ind; ++i)
        printf("%f %f\n", st[i].x, st[i].y);
    return 0;
}