Cod sursa(job #2276776)

Utilizator giotoPopescu Ioan gioto Data 5 noiembrie 2018 12:28:59
Problema Infasuratoare convexa Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.09 kb
#include <bits/stdc++.h>
using namespace std;

struct point{
    double x, y;
};

int n;
int st[120005];
point a[120005];

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

inline bool cmp(point A, point B){
    return det(a[1], A, B) < 0;
}

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

    scanf("%d", &n);
    int w = 0;
    double x = 2000000000.0;
    for(int i = 1; i <= n ; ++i){
        scanf("%lf%lf", &a[i].x, &a[i].y);
        if(a[i].x < x) x = a[i].x, w = i;
        else if(a[i].x == x && a[i].y < a[w].y) w = i;
    }

    swap(a[1], a[w]);
    sort(a + 2, a + n + 1, cmp);

    int top = 0;
    st[++top] = 1;
    st[++top] = 2;

    for(int i = 3; i <= n ; ++i){
        while(top >= 2 && det(a[st[top - 1]], a[st[top]], a[i]) > 0)
            --top;
        st[++top] = i;
    }

    printf("%d\n", top);
    for(int i = top; i >= 1 ; --i)
        printf("%0.12f %0.12f\n", a[st[i]].x, a[st[i]].y);


    return 0;
}