Cod sursa(job #2835399)

Utilizator BalasaRaduBalasa Radu BalasaRadu Data 18 ianuarie 2022 17:41:10
Problema Infasuratoare convexa Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.21 kb
#include <bits/stdc++.h>
using namespace std;

ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");

const int dim=200000;

struct pt{
    long double x,y;
    int ind;
    bool operator<(const pt &other) const
    {
        if(x==other.x){
            return y<other.y;
        }
        return x<other.x;
    }
}v[dim];

long double top,bottom;
bool ap[dim];
vector<pt>e;

void solve(){
    ap[0]=true;
    top=e[0].y,bottom=e[0].y;
    for(auto it:e){
        long double y=it.y;
        int ind=it.ind;
        if(y>=top){
            ap[ind]=true;
            top=y;
        }
        if(y<=bottom){
            ap[ind]=true;
            bottom=y;
        }
    }
}

signed main(){
    int n;
        fin>>n;
    for(int i=1;i<=n;i++){
        fin>>v[i].x>>v[i].y;
        e.push_back({v[i].x,v[i].y,i});
    }
    sort(e.begin(),e.end());
    solve();
    reverse(e.begin(),e.end());
    solve();
    int nr=0;
    for(int i=1;i<=n;i++){
        if(ap[i]){
            nr++;
        }
    }
            fout<<nr<<'\n';
    for(int i=1;i<=n;i++){
        if(ap[i]){
            fout<<fixed<<setprecision(6)<<v[i].x<<' '<<v[i].y<<'\n';
        }
    }
}