Cod sursa(job #3252711)

Utilizator StefanStratonStefan StefanStraton Data 30 octombrie 2024 19:05:14
Problema Infasuratoare convexa Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.52 kb
#include <fstream>
#include <algorithm>
#include <iomanip>

using namespace std;

ifstream cin("infasuratoare.in");
ofstream cout("infasuratoare.out");

struct ura{
    double x, y;
    int parte = 0;
} v[120005];

bool cmp(ura a, ura b){
    if(a.x < b.x) return true;
    if(a.x > b.x) return false;
    if(a.y < b.y) return true;
    if(a.y > b.y) return false;
}

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

int st[120005];

int main(){

    int n; cin >> n;

    for(int i = 1; i <= n; i++) cin >> v[i].x >> v[i].y;

    sort(v+1, v+n+1, cmp);

    ura a = v[1], b = v[n];

    for(int i = 2; i <= n-1; i++)
        if(det(a, b, v[i]) < 0) v[i].parte = 1; /// jos
        else v[i].parte = 2; /// deasupra ab

    int vf = 1;
    st[1] = 1;

    for(int i = 2; i <= n; i++){
        if(v[i].parte == 1 || v[i].parte == 0){
            while(vf > 1 && det(v[st[vf-1]], v[st[vf]], v[i]) < 0)
                vf--;
            vf++;
            st[vf] = i;
        }
    }

    int cvf = vf;
    st[vf] = n;

    for(int i = n - 1; i >= 1; i--){
        if(v[i].parte == 2 || v[i].parte == 0){
            while(vf > cvf && det(v[st[vf-1]], v[st[vf]], v[i]) < 0)
                vf--;
            vf++;
            st[vf] = i;
        }
    }

    cout << vf - 1 << '\n';
    for(int i = 1; i <= vf - 1; i++)
        cout << fixed << setprecision(6) << v[st[i]].x << " " << v[st[i]].y << '\n';

    return 0;
}