Cod sursa(job #2835592)

Utilizator BalasaRaduBalasa Radu BalasaRadu Data 18 ianuarie 2022 22:26:53
Problema Infasuratoare convexa Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.64 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;
}v[dim];

bool cmp1(pt a,pt b){
    if(a.x==b.x){
        return a.y<b.y;
    }
    return a.x<b.x;
}

bool cmp2(pt a,pt b){
    if(a.x==b.x){
        return a.y>b.y;
    }
    return a.x<b.x;
}

int ap[dim];
vector<pt>e;

int n,stiva[dim],vf;

long double determinat(pt A,pt B,pt 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 ccw(pt A,pt B,pt C){
    return determinat(A,B,C)>0;
}

void solve(){
    sort(e.begin(),e.end(),cmp1);
    vf=0;
    for(auto it:e){
        long double y=it.y;
        int ind=it.ind;
        while(vf>=2 && !ccw(v[stiva[vf-1]],v[stiva[vf]],v[ind])){
            ap[stiva[vf]]--;
            vf--;
        }
        stiva[++vf]=ind;
        ap[ind]++;
    }
    sort(e.begin(),e.end(),cmp2);
    vf=0;
    for(auto it:e){
        long double y=it.y;
        int ind=it.ind;

        while(vf>=2 && ccw(v[stiva[vf-1]],v[stiva[vf]],v[ind])){
            ap[stiva[vf]]--;
            vf--;
        }
        stiva[++vf]=ind;
        ap[ind]++;
    }
}

signed main(){
        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});
    }
    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';
        }
    }
}