Cod sursa(job #2544148)

Utilizator Stefan_PiscuPiscu Stefan Constantin Stefan_Piscu Data 11 februarie 2020 20:09:19
Problema Infasuratoare convexa Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.98 kb
#include <bits/stdc++.h>
using namespace std;

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

struct point{
    double x, y;
    int poz;
    bool operator<(point b){
        return x==b.x?y<b.y:x<b.x;
    }
    point operator- (point a){
        return {x-a.x, y-a.y};
    }
};

double cp(point o, point a, point b){
    a=a-o, b=b-o;
    return a.x*b.y-a.y*b.x;
}

vector<point> hull(vector<point> v){
        vector<point> sol;
        for(int i=0,p=1;i>=0;i+=(p=i==(v.size()-1)?-p:p)){
            while(sol.size()>=2&&cp(sol[sol.size()-2], sol[sol.size()-1], v[i])<0) sol.pop_back();
            sol.push_back(v[i]);
        }
        sol.pop_back();
        return sol;
}
int main(){
  int n;
  fin>>n;
  vector<point> v;
  for(int i=0;i<n;++i){
    point x;
    fin>>x.x>>x.y;
    v.push_back(x);
  }
  v=hull(v);
  fout<<v.size()<<"\n";
  for(auto i:v){
    fout<<fixed<<setprecision(10)<<i.x<<" "<<i.y<<"\n";
  }
  return 0;
}