Cod sursa(job #2316679)

Utilizator DimaTCDima Trubca DimaTC Data 12 ianuarie 2019 11:30:51
Problema Infasuratoare convexa Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.94 kb
#include<bits/stdc++.h>
#define pdd pair<double, double>
#define N 120010
#define x first
#define y second
using namespace std;

int n, mn;
pdd a[N];
pdd s[N];

int det(pdd A, pdd B, pdd C) {
    return A.x*B.y+B.x*C.y+C.x*A.y-B.y*C.x-C.y*A.x-A.y*B.x;
}

bool cmp(pdd l, pdd r) {
    return (det(a[1],l,r)>0);
}

int main() {
    ifstream cin("infasuratoare.in");
    ofstream cout("infasuratoare.out");
    cin>>n; a[0] = {1e9+1,0};
    for (int i=1; i<=n; ++i) {
        cin>>a[i].x>>a[i].y;
        if (a[i].x<a[mn].x || a[i].x==a[mn].x && a[i].y < a[mn].y) mn=i;
    }
    swap(a[1],a[mn]);
    sort(a+1,a+1+n,cmp);

    int last=2;
    s[1]=a[1], s[2]=a[2];
    for (int i=3; i<=n; ++i) {
        while (last>=3 && det(s[last-1], s[last], a[i])<0) last--;
        s[++last]=a[i];
    }
    cout<<last<<'\n';
    for (int i=1; i<=last; ++i) cout<<fixed<<setprecision(12)<<s[i].x<<" "<<s[i].y<<'\n';

    return 0;
}