Cod sursa(job #2392376)

Utilizator VladTiberiuMihailescu Vlad Tiberiu VladTiberiu Data 29 martie 2019 22:16:18
Problema Infasuratoare convexa Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.37 kb
#include <bits/stdc++.h>

using namespace std;

ifstream f("infasuratoare.in");
ofstream g("infasuratoare.out");

struct point{
    long double x,y;
};

const long double INF = 1000000003;
const int NMax = 120005;

point a[NMax];
int n,top,ind;
int st[NMax];

long double unghi(point A, point B, point C){
    return (A.y - B.y) * (A.x - C.x) - (A.y - C.y) * (A.x - B.x);
}
bool cmp(point x, point y){
    return unghi(a[1], x, y) > 0;
}
int main(){
    ifstream cin("infasuratoare.in");
    ofstream cout("infasuratoare.out");
    cin >> n;
    int mn_x = INF, mn_y = INF;
    for(int i = 1; i <= n; ++i){
        cin >> a[i].x >> a[i].y;
        if(a[i].x == mn_x){
            if(a[i].y < mn_y){
                mn_x = a[i].x;
                mn_y = a[i].y;
                ind = i;
            }
        }
        if(a[i].x < mn_x){
            mn_x = a[i].x;
            mn_y = a[i].y;
            ind = i;
        }
    }
    swap(a[1], a[ind]);
    sort(a + 2, a + 1 + n, cmp);
    st[++top] = 1;
    st[++top] = 2;

    for(int i = 3; i <= n; ++i){
        while(unghi(a[st[top - 1]], a[st[top]], a[i]) < 0){
            top--;
        }
        st[++top] = i;
    }
    cout << top << '\n';
    for(int i = top; i >= 1; --i){
        cout << fixed << setprecision(12) << a[st[i]].x << ' ' << a[st[i]].y << '\n';
    }
    return 0;
}