Cod sursa(job #1468760)

Utilizator bogdan10bosBogdan Sitaru bogdan10bos Data 6 august 2015 21:59:04
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.58 kb
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <ctime>
#include <cmath>
#include <algorithm>
#include <vector>
#include <queue>
#include <deque>

#define INF ( (1 << 30) - 1 + (1 << 30) )
#define mod 666013
#define eps 1e-12

using namespace std;

struct punct
{
    double x, y;
}v[120005];

int n, i, q, st[120005], ap[120005];

bool cmp(punct a, punct b)
{
    if( fabs(a.x - b.x) < eps) return a.y < b.y;
    return a.x < b.x;
}

double det(punct a, punct b, punct c)
{
    return (double)( a.x * b.y + b.x * c.y + c.x * a.y - a.y * b.x - b.y * c.x - c.y * a.x );
}

int main()
{
    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);
    sort(v + 1, v + n + 1, cmp);

    st[1] = 1;
    st[2] = 2;
    ap[2] = 1;
    q = 2;

    for(i = 3; i <= n; i++)
    {
        if(ap[i])
            continue;
        while(q >= 2 && det( v[ st[q - 1] ], v[ st[q] ], v[i] ) < eps)
        {
            ap[ st[q] ] = 0;
            q--;
        }
        st[ ++q ] = i;
        ap[i] = 1;
    }

    for(i = n; i > 0; i--)
    {
        if(ap[i])
            continue;
        while(q >= 2 && det( v[ st[q - 1] ], v[ st[q] ], v[i] ) < eps)
        {
            ap[ st[q] ] = 0;
            q--;
        }
        st[ ++q ] = i;
        ap[i] = 1;
    }

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