Cod sursa(job #2402634)

Utilizator cyg_vladioanBirsan Vlad cyg_vladioan Data 10 aprilie 2019 21:05:25
Problema Infasuratoare convexa Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.43 kb
#include <cstdio>
#include <algorithm>
#include <cmath>
using namespace std;
const int INF = 2.e9;
const double PI = 2.0 * acos(0.0);
const double eps = 1.e-12;
struct POINT
{
    double x, y;
};
POINT P[120005] , aux;
double cp(POINT P1, POINT P2, POINT P3)
{
    return (P2.x - P1.x) * (P3.y - P2.y) - (P2.y - P1.y) * (P3.x - P2.x);
}
double cmp(POINT a, POINT b)
{
    return cp(P[1] , a , b) < 0;
}
int ccw(POINT P1, POINT P2, POINT P3)
{
    double ccp;
    ccp = cp(P1, P2, P3);
    if(fabs(ccp) < eps)
        return 0;
    if(ccp > eps)
        return 1;
    return -1;
}
int st[120005];
int main()
{
    freopen("infasuratoare.in", "r", stdin);
    freopen("infasuratoare.out", "w", stdout);
    int n, i, ind, top , poz;
    double tx, ty;
    scanf("%d", &n);
    for(i = 1 ; i <= n ; i ++)
    {
        scanf("%lf%lf", &tx, &ty);
        P[i].x = tx;
        P[i].y = ty;
    }
    poz = 1;
    for(i = 2 ; i <= n ; i ++)
        if(P[i].x < P[poz].x)
            poz = i;
    aux = P[poz];
    P[poz] = P[1];
    P[1] = aux;
    sort(P + 2, P + n + 1, cmp);
    top = 2;
    st[1] = 1;
    st[2] = 2;
    for(i = 3 ; i <= n ; i ++)
    {
        while(top >= 2 && ccw(P[st[top - 1]], P[st[top]], P[i]) != -1)
            top --;
        st[++ top] = i;
    }
    printf("%d\n", top);
    for(i = top ; i >= 1 ; i --)
        printf("%f %f\n", P[st[i]].x, P[st[i]].y);
    return 0;
}