Cod sursa(job #2233842)

Utilizator AlexandruRudiAlexandru Rudi AlexandruRudi Data 24 august 2018 16:02:38
Problema Infasuratoare convexa Scor 20
Compilator cpp Status done
Runda Arhiva educationala Marime 1.73 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;

bool comp(pld a, pld b){
    int p,q;
    if(a.x==x) p=0;
    else if(a.x<x) p=1;
    else p=-1;
    if(b.x==x) q=0;
    else if(b.x<x) q=1;
    else q=-1;
    if(p!=q) return p<q;
    else if(p==0) return a.y<b.y;
    else return (a.y-y)/(a.x-x)<(b.y-y)/(b.x-x);
}

ld det(ll a, ll b, ll c, ll d, ll e, ll f, ll g, ll h, ll i){
    return a*e*i+b*f*g+c*d*h-c*e*g-f*h*a-i*b*d;
}

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(det(x.x,x.y,1,y.x,y.y,1,z.x,z.y,1)<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';
    }
}