Cod sursa(job #2793386)

Utilizator Ronnie007Radostin Chonev Ronnie007 Data 3 noiembrie 2021 16:30:48
Problema Infasuratoare convexa Scor 60
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.91 kb
#include<bits/stdc++.h>
using namespace std ;


using Point = complex<double>;

const double kPi = 4.0 * atan(1.0);
const double kEps = 1e-9; // Good eps for long double is ~1e-11

#define X() real()
#define Y() imag()

double dot(Point a, Point b) { return (conj(a) * b).X(); }
double cross(Point a, Point b) { return (conj(a) * b).Y(); }
double dist(Point a, Point b) { return abs(b - a); }
Point perp(Point a) { return Point{-a.Y(), a.X()}; } // +90deg

Point rotateCCW(Point a, double theta) {
  return a * polar(1.0, theta); }
double det(Point a, Point b, Point c) {
  return cross(b - a, c - a); }

// abs() is norm (length) of vector
// norm() is square of abs()
// arg() is angle of vector
// det() is twice the signed area of the triangle abc
// and is > 0 iff c is to the left as viewed from a towards b.
// polar(r, theta) gets a vector from abs() and arg()

void ExampleUsage() {
  Point a{1.0, 1.0}, b{2.0, 3.0};
  cerr << a << " " << b << endl;
  cerr << "Length of ab is: " << dist(a, b) << endl;
  cerr << "Angle of a is: " << arg(a) << endl;
  cerr << "axb is: " << cross(a, b) << endl;
}

using Poly = vector<Point>;
pair<Poly, Poly> ConvexHull(Poly P) {
  sort(P.begin(), P.end(), [](Point a, Point b) {
    return make_pair(a.X(), a.Y()) < make_pair(b.X(), b.Y());
  });
  P.erase(unique(P.begin(), P.end()), P.end());

  Poly up, dw;
  for (auto p : P) {
    while (up.size() >= 2 &&
           det(up[up.size() - 2], up.back(), p) > 0) // (1)
      up.pop_back();
    up.push_back(p);

    while (dw.size() >= 2 &&
          det(dw[dw.size() - 2], dw.back(), p) < 0) // (2)
      dw.pop_back();
    dw.push_back(p);
  }
  return { up , dw } ;
}

#define MAXN 50007

int n ;
pair < double , double > a[ MAXN ] ;

Poly aux ;

void input ( ) {
    cin >> n ;
    for ( int i = 1 ; i <= n ; ++ i ) {
        cin >> a[ i ].first >> a[ i ].second ;
        aux.push_back ( { a[ i ].first , a[ i ].second } ) ;
    }
}

void solve ( ) {
    auto ret = ConvexHull ( aux ) ;
    cout << ret.first.size ( ) + ret.second.size ( ) - 2 << "\n" ;
    ret.second.pop_back ( ) ;
    reverse ( ret.second.begin ( ) , ret.second.end ( ) ) ;
    ret.second.pop_back ( ) ;
    reverse ( ret.first.begin ( ) , ret.first.end ( ) ) ;
    reverse ( ret.second.begin ( ) , ret.second.end ( ) ) ;
    swap ( ret.first , ret.second ) ;
    for ( auto e : ret.first ) {
        cout << fixed << setprecision ( 12 ) << e.X() << " " << e.Y() << "\n" ;
    }
    for ( auto e : ret.second ) {
        cout << fixed << setprecision ( 12 ) << e.X() << " " << e.Y() << "\n" ;
    }
}

int main ( ) {
    freopen ( "infasuratoare.in" , "r" , stdin ) ;
    freopen ( "infasuratoare.out" , "w" , stdout ) ;
    /// ios_base :: sync_with_stdio ( false ) ;
    /// cin.tie ( NULL ) ;
    int t ;
    t = 1 ;
    /// scanf ( "%d" , &t ) ;
    /// cin >> t ;
    while ( t -- ) {
        input ( ) ;
        solve ( ) ;
    }
    return 0 ;
}