Cod sursa(job #2953520)

Utilizator vlad_dimuVlad Dimulescu vlad_dimu Data 11 decembrie 2022 16:59:08
Problema Infasuratoare convexa Scor 10
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.34 kb
#include <fstream>
#include <algorithm>
#include <vector>
#include <iomanip>
#define MAXN 120000
#define PRECIZIE 1e-12
using namespace std;

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

struct Point{
  double x, y;
}v[MAXN + 1];

vector <int> hull;

inline double orientation(const Point& a, const Point& b, const Point& c) {
    return (b.y - a.y) * (c.x - b.x) - (b.x - a.x) * (c.y - b.y);
}

inline bool cmpPoint(const Point& a, const Point& b) {
    return orientation(v[0], a, b) < 0;
}

int main(){
    int n, i, start;
    fin >> n;
    for( i = 0; i < n; i++ )
      fin >> v[i].x >> v[i].y;

    start = 0;
    for( i = 1; i < n; i++ )
      if( v[i].y < v[start].y || (v[i].y == v[start].y && v[i].x < v[start].x ) )
        start = i;

    Point aux;
    aux = v[0];
    v[0] = v[start];
    v[start] = v[0];

    sort( v + 1, v + n, cmpPoint );

    hull.push_back(0);
    hull.push_back(1);

    for( i = 2; i < n; i++ ){
      while( hull.size() >= 2 && orientation( v[ hull[hull.size() - 2] ], v[hull.back()], v[i] ) >= 0 )
        hull.pop_back();

      hull.push_back(i);
    }
    fout << hull.size() <<'\n';
    fout << setprecision(6) << fixed;
    for( i = 0; i < hull.size(); i++ )
      fout << v[ hull[i] ].x << ' ' << v[ hull[i] ].y << '\n';

    return 0;
}