Cod sursa(job #2233850)

Utilizator AlexandruRudiAlexandru Rudi AlexandruRudi Data 24 august 2018 16:11:06
Problema Infasuratoare convexa Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.46 kb
#pragma GCC optimize ("O3")
#include <bits/stdc++.h>
using namespace std;
#define x first
#define y second
#define dbg(x) cout << #x << '=' << x << '\n';
#define ll long long
#define pi pair<int,int>
#define pl pair<ll,ll>
#define pd pair<double,double>
#define ld long double
#define pld pair<ld,ld>
#define lg length()
#define sz size()
#define pb push_back
#define MAXN 100005
#define INF 1000000005
#define LINF 1000000000000000005
#define x1 xdddddddddddddddddd
#define y1 ydddddddddddddddddd

int n,id;

pld a[120005];

ld x,y=LINF;

ld cp(pld a, pld b, pld c){
    return (b.y-a.y)*(c.x-a.x)-(b.x-a.x)*(c.y-a.y);
}

bool comp(pld x, pld y){
    return cp(a[1],x,y)<0;
}

int32_t main(){
    ios_base :: sync_with_stdio(0); cin.tie(); cout.tie();
    //ifstream cin("infasuratoare.in");
    //ofstream cout("infasuratoare.out");
    cin >> n;
    for(int i=1;i<=n;i++){
        cin >> a[i].x >> a[i].y;
        if(a[i].y<y) y=a[i].y,x=a[i].x,id=i;
        else if(a[i].y==y && a[i].x<x) x=a[i].x,id=i;
    }
    swap(a[1],a[id]);
    sort(a+2,a+n+1,comp);
    vector <pld> p;
    p.pb({x,y});
    for(int i=2;i<=n;i++){
        while(p.sz>1){
            pld x=p[p.sz-2],y=p[p.sz-1],z=a[i];
            if(cp(x,y,z)>0) p.pop_back();
            else break;
        }
        p.pb(a[i]);
    }
    cout << p.sz << '\n';
    cout << fixed << setprecision(13);
    for(pld i : p){
        cout << i.x << ' ' << i.y << '\n';
    }
}