Cod sursa(job #2774224)

Utilizator RobertAcAcatrinei Robert-Marian RobertAc Data 10 septembrie 2021 16:12:10
Problema Infasuratoare convexa Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.1 kb
#include <bits/stdc++.h>
#define x first
#define y second
#define nmax 120000
using namespace std;
string prob="infasuratoare";
ifstream in(prob+".in");
ofstream out(prob+".out");
int n;
bool eval(pair<double,double> a,pair<double,double> b,pair<double,double> p){
    return (b.x-a.x)*(p.y-a.y)-(p.x-a.x)*(b.y-a.y)<=0;
}
vector<pair<double,double>> infasuratoare(vector<pair<double,double>> v){
    vector<pair<double,double>> res(nmax);
    sort(v.begin(),v.end());
    int k=0;
    for(int i=0;i<n;i++){
        while(k>=2&&eval(res[k-2],res[k-1],v[i]))k--;
        res[k++]=v[i];
    }
    for(int i=n-1,t=k+1;i>0;i--){
        while(k>=t&&eval(res[k-2],res[k-1],v[i-1]))k--;
        res[k++]=v[i-1];
    }
    res.resize(k-1);
    return res;
}
int main(){
    vector<pair<double,double>> v;
    in>>n;
    double x,y;
    for(int i=0;i<n;i++){
        in>>x>>y;
        v.push_back({x,y});
    }
    v=infasuratoare(v);
    out<<v.size()<<'\n';
    v.push_back(*v.begin());
    for(int i=1;i<v.size();i++){
        out<<fixed<<setprecision(6)<<v[i].x<<' '<<v[i].y<<'\n';
    }
}