Cod sursa(job #2835633)

Utilizator BalasaRaduBalasa Radu BalasaRadu Data 18 ianuarie 2022 23:48:01
Problema Infasuratoare convexa Scor 30
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.44 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];
vector<pt>ans;

int ind;
pt CENTRU;
vector<pt>e;

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;
}
bool cmp(pt A,pt B){
    return ccw(e[0],A,B);
}

int ap[dim],stiva[dim],vf;

bool cross(pt a,pt b,pt c){
    return (b.x-a.x)*(c.y-a.y)-(b.y-a.y)*(c.x-a.x)<=0;
}

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

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

signed main(){
    int n;
    CENTRU.x=1e9,CENTRU.y=1e9,ind=0;
        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});
        if(v[i].x<CENTRU.x){
            CENTRU=v[i];
            ind=i;
        }
        if(v[i].x==CENTRU.x){
            if(v[i].y<CENTRU.y){
                CENTRU=v[i];
                ind=i;
            }
        }
    }
    sort(e.begin(),e.end());
    solve();
    for(int i=1;i<=n;i++){
        if(ap[i]){
            ans.push_back(v[i]);
        }
    }
    sort(ans.begin(),ans.end(),cmp);
            fout<<ans.size()<<'\n';
    int ok=false;
        for(auto it:ans){
            if(it.x==v[ind].x&&it.y==v[ind].y){
                ok=1;
            }
                if(ok){
                    fout<<fixed<<setprecision(12)<<it.x<<' '<<it.y<<'\n';
                }
        }
        for(auto it:ans){
            if(it.x==v[ind].x&&it.y==v[ind].y){
                return 0;
            }
                if(ok){
                    fout<<fixed<<setprecision(12)<<it.x<<' '<<it.y<<'\n';
                }
        }
}