Cod sursa(job #2142435)

Utilizator alittlezzCazaciuc Valentin alittlezz Data 25 februarie 2018 00:02:02
Problema Infasuratoare convexa Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.69 kb
#include <bits/stdc++.h>

using namespace std;

const int N = 120'005;

pair <double, double> v[N];
pair <double, double> ax[N];
pair <double, double> st[N];

int signDet(pair<double, double> A, pair<double, double> B, pair<double, double> C){
    double det = A.first * B.second + B.first * C.second + C.first * A.second - A.first * C.second - C.first * B.second - B.first * A.second;
    if(det == 0){
        return 0;
    }
    return (det < 0 ? 1 : -1);
}

bool comp(pair<double, double> A, pair<double, double> B){
    int sg = signDet(v[1], A, B);
    if(sg == 0){
        return A.first < B.first;
    }
    return sg < 0;
}

int main(){
    freopen("infasuratoare.in", "r", stdin);
    freopen("infasuratoare.out", "w", stdout);
    int n;
    scanf("%d", &n);
    int id = 0;
    for(int i = 1;i <= n;i++){
        scanf("%lf %lf", &v[i].first, &v[i].second);
        if(i == 1){
            id = i;
        }else if(v[i].second < v[id].second){
            id = i;
        }else if(v[i].second == v[id].second && v[i].first < v[id].first){
            id = i;
        }
    }
    swap(v[1], v[id]);
    sort(v + 2, v + n + 1, comp);
    int nn = 0;
    for(int i = 2;i < n;i++){
        if(signDet(v[1], v[i], v[i + 1]) == 0){
            continue;
        }
        ax[++nn] = v[i];
    }
    ax[++nn] = v[n];
    st[1] = v[1];
    st[2] = ax[1];
    int e = 2;
    for(int i = 2;i <= nn;i++){
        while(e > 1 && signDet(st[e - 1], st[e], ax[i]) > 0){
            e--;
        }
        st[++e] = ax[i];
    }
    printf("%d\n", e);
    for(int i = 1;i <= e;i++){
        printf("%.8f %.8f\n", st[i].first, st[i].second);
    }
    return 0;
}