Cod sursa(job #2474999)

Utilizator greelioGreenio Greely greelio Data 16 octombrie 2019 00:16:49
Problema Infasuratoare convexa Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.93 kb
#include<bits/stdc++.h>
#define N 121010
#define x first
#define y second

using namespace std;

typedef pair<double,double> point;

int n,mn;
point a[N],O;

double det(point A, point B, point 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(point l, point r) {
    return (det(a[1], l,r)>0);
}

int main() {
    ifstream cin("infasuratoare.in");
    ofstream cout("infasuratoare.out");
    cin>>n; mn=1;
    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+2,a+1+n, cmp);

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


    return 0;
}