Language: C++

/**
 * @brief 凸包の構成について扱います
 *
 * @note  点集合Qの各点がその境界上か内部にある最小の凸多角形PをQの凸包(convex hull)と言い、CH(Q)で表す
 *        集合Qの点はすべて異なり、同一直線上にはない3点を少なくとも含むと仮定する
 *        直観的には、Qの各点を板から突き出した釘であると考えることができる. これらすべての釘を取り囲む、強い輪ゴムが作る形状が凸包である
 *
 * @note  関連URL: http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=CGL_4_A&lang=jp
 *
 * @date  2016/03/21
 */


//****************************************
// 必要なヘッダファイルのインクルード
//****************************************

#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <functional>



/****************************************
// オブジェクト形式マクロの定義
//****************************************

//#define GEOMETRY_BEGIN namespace geom {
//#define GEOMETRY_END }



//****************************************
// 型シノニム
//****************************************

using coord_t    = long double;
using index_t    = std::int32_t;
using indices_t  = std::vector<index_t>;



//****************************************
// 構造体の定義
//****************************************

struct point {
    coord_t x, y;
    point() : x(0), y(0) {}
    point(coord_t x, coord_t y) : x(x), y(y) {}

    point& operator+=(const point& p)  { x += p.x; y += p.y; return *this; }
    point& operator-=(const point& p)  { x -= p.x; y -= p.y; return *this; }
    point& operator*=(const coord_t d) { x *= d; y *= d; return *this;}

    point operator+(const point& p)  const { return point(*this) += p; }
    point operator-(const point& p)  const { return point(*this) -= p; }
    point operator*(const coord_t d) const { return point(*this) *= d; }
};


struct segment {
    point ps;  // 線分の始点
    point pd;  // 線分の終点
};



namespace limits {
    constexpr auto pi  = 3.141592653589793238;
    constexpr auto eps = 1e-10;
    constexpr auto inf = 1e12;
}


/**
 * @brief   与えられた3点a, b, cをa -> b -> cと進むとき、
 * @details a -> bで時計方向に折れてb -> c (cw)
 *          a -> bで反時計方向に折れてb -> c (ccw)
 *          a -> bで逆を向いてaを通り越してb -> c (back)
 *          a -> bでそのままb -> c (front)
 *          a -> bで逆を向いてb -> cまたは、b == c (on)
 */
enum struct ffd {  // front face direciton
    cw    = -1,
    ccw   = +1,
    back  = +2,
    front = -2,
    on    = 0,
};



/**
 * @brief 述語オブジェクト
 */
struct cmp_x { bool operator()(const point& pi, const point& pj) { return pi.x < pj.x; } };
struct cmp_y { bool operator()(const point& pi, const point& pj) { return pi.y < pj.y; } };



//****************************************
// 型シノニムその2
//****************************************

using vector_t   = point;
using polygon_t  = std::vector<point>;
using segments_t = std::vector<segment>;



//****************************************
// 関数の定義
//****************************************

/**
 * @brief  2つのベクトルa, bからなる行列A = (a, b)の行列式(determinant)を返します
 * @param  const vector_t& a ベクトルa
 * @param  const vector_t& b ベクトルb
 * @return coord_t det(A)    行列式|(a, b)|
 */
static constexpr coord_t det(const vector_t& a, const vector_t& b)
{
    return a.x * b.y - a.y * b.x;
}


/**
 * @brief  2つのベクトルa, bのクロス積(cross product)a x bを返します
 * @param  const vector_t& a  ベクトルa
 * @param  const vector_t& b  ベクトルb
 * @return coord_t a x b      クロス積a x b
 */
static constexpr coord_t cross(const vector_t& a, const vector_t& b)
{
    return a.x * b.y - a.y * b.x;
    //return det(a, b);
}


/**
 * @brief  2つのベクトルa, bのドット積(dot product)a・bを返します
 * @param  const vector_t& a  ベクトルa
 * @param  const vector_t& b  ベクトルb
 * @return coord_t a・b       ドット積a・b
 */
static constexpr coord_t dot(const vector_t& a, const vector_t& b)
{
    return a.x * b.x + a.y * b.y;
}


/**
 * @brief  ベクトルvの大きさの2乗を返します
 * @param  const vector_t& v
 * @return coord_t norm(v);
 */
static constexpr coord_t abs2(const vector_t& v)
{
    return v.x * v.x + v.y * v.y;
    // return dot(v, v);
}


/**
 * @brief  ベクトルvの大きさ|v|(原点からの距離)を返します
 * @param  const vector_t& v
 * @return coord_t sqrt(norm(v))
 */
static inline coord_t abs(const vector_t& v)
{
    return std::sqrt(abs2(v));
}


/**
 * @brief  点pから線分sに下ろした垂線と線分sの交点を返します
 * @param  const segment& s 線分s
 * @param  const point& p   点p
 * @return 垂線と線分の交点
 */
static inline point proj(const segment& s, const point& p)
{
    vector_t base = s.pd - s.ps;
    vector_t hypo = p - s.ps;
    coord_t r = dot(hypo, base) / abs2(base);
    return s.ps + base * r;
}


/**
 * @brief  点pと線対称の位置に存在する点を返します
 * @param  cosnt segment& s 線分s
 * @param  const point&   p 点p
 * @param  pと線対称な点
 */
static inline point reflect(const segment& s, const point p)
{
    return p + (proj(s, p) - p) * 2.0;
}


/**
 * @brief COMBINED-TOLERANCE-COMPAREより少ない労力で行える近似的な判定
 */
static inline bool approximate_combined_tolerance_compare(coord_t x, coord_t y) noexcept
{
    return std::fabs(x - y) <= limits::eps * (std::fabs(x) + std::fabs(y) + 1.0);
}


/**
 * @brief 手続きAPPROXIMATE-COMBINED-TOLERANCE-COMPAREの短い名前
 */
static inline bool eq(coord_t x, coord_t y)
{
    return approximate_combined_tolerance_compare(x, y);
}


/**
 * @brief 述語オブジェクト
 */
struct cmp_xy { bool operator()(const point& pi, const point& pj) { return pi.x < pj.x || (eq(pi.x, pj.x) && pi.y < pj.y); } };


/**
 * @brinf 2点(p1, p2)のp0に関する偏角(polar angle)から、
 *        p0から見た2つのベクトルp0p1↑, p0p2↑の方向を返す
 */
static inline ffd ccw(point p0, point p1, point p2)
{
    p1 -= p0; p2 -= p0;

    if (cross(p1, p2) > limits::eps)  { return ffd::ccw;  }  // クロス積(p1-p0)x(p2-p0)が正の場合、ccw  ...(*1)
    if (cross(p1, p2) < -limits::eps) { return ffd::cw;   }  // クロス積(p1-p0)x(p2-p0)が負の場合、cw   ...(*2)


    // (*1), (*2)に当てはまらないとき、p2は直線p0p1|上(線分p0p1↑上とは限らない)に存在する

    if (dot(p1, p2) < -limits::eps)   { return ffd::back;  }  // ドット積(p1-p0)・(p2-p0)が負の場合、p2->p0->p1(back) ...(*3)

    // (*3)に当てはまらないとき、p2はp0->p1->p2またはp0->p2->p1の位置に存在する

    if (eq(abs2(p1), abs2(p2)))       { return ffd::front; }  // p0p2↑の大きさがp0p1↑の大きさより大きい場合、p0->p1->p2(front) ...(*4)

    // (*4)に当てはまらないとき、p0->p2->p1(on)
    return ffd::on;
}


/**
 * @brief  平面上の点集合Pを入力として取り、その凸包CH(P)の点を時計回りの順に並べたリストを返します
 *
 * @note   入力は|P| >= 3を仮定する. それに反した場合、空のリストを返す
 * @note   実行時間はΟ(nlgn)
 *
 * @param  polygon_t& P 点集合P
 * @param  bool degenerate 縮退した場合を考慮するか否か(3点が同一直線上にあるとき、中央の点を含めないならtrue, 含めるならfalse)
 * @return polygon_t CH(P) Pを含む凸集合
 */
polygon_t andrew_scan(polygon_t& P, bool degenerate)
{
    index_t n = P.size(), k = 0;

    if (n < 3) { return { }; }  // |P| >= 3を仮定する

    // 与えられた点の中からすべての点を左から右に順序付けする
    std::sort(P.begin(), P.end(), cmp_xy());  // NOTE: xが等しい場合、yの昇順とする

    // 上側チェーンと下側チェーンを構成する(それぞれ凸包の上半分と下半分に相当する)
    polygon_t L(2 * n);  // NOTE: Pの点を1点ずつ加えながら解を更新する

    // 縮退した場合を考慮するか否かを決定する述語を設定する
    auto pred = degenerate
        ? std::function<bool(index_t, index_t)>([&](index_t i, index_t k) -> bool { return ccw(L[k - 2], L[k - 1], P[i]) != ffd::ccw; })
        : std::function<bool(index_t, index_t)>([&](index_t i, index_t k) -> bool { return ccw(L[k - 2], L[k - 1], P[i]) == ffd::cw;  });
                            

    // まず、凸包上の点の中で上部凸包(upper hull)上にあるものだけ求める
    for (index_t i = 0; i < n; i++) {
        while (k >= 2 && pred(i, k)) { k = k - 1; }
        L[k] = P[i]; k = k + 1;
    }

    // 右から左へと実行される2番目の走査で、凸包の残りの部分、すなわち下部凸包(lower hull)を計算する
    for (index_t i = n - 2, t = k + 1; i >= 0; i--) {
        while (k >= t && pred(i, k)) { k = k - 1; }
        L[k] = P[i]; k = k + 1;
    }

    L.resize(k - 1);  // CH(P)の頂点を時計回りの順に並べたリストL
    return L;         // リストLを返す
}



//****************************************
// エントリポイント
//****************************************

int main()
{
    using namespace std;
    int n;
    cin >> n;

    polygon_t poly(n);
    for (int i = 0; i < n; i++) {
        coord_t x, y;
        cin >> x >> y;
        poly[i] = point(x, y);
    }

    polygon_t convex_hull = andrew_scan(poly, false);

    index_t m = convex_hull.size();
    cout << m << endl;

    index_t min_x, min_y, min_i;
    min_x = min_y = std::numeric_limits<index_t>::max();
    for (index_t i = 0; i < n; i++) {
        if (min_y > convex_hull[i].y || (min_y == convex_hull[i].y && min_x > convex_hull[i].x)) {
            min_x = convex_hull[i].x;
            min_y = convex_hull[i].y;
            min_i = i;
        }
    }
    
    for (index_t i = 0; i < m; i++) {
        cout << convex_hull[(min_i + i) % m].x << " " << convex_hull[(min_i + i) % m].y << endl;
    }
    
    return 0;
}

Compiler output:
a.cc:99:38: error: 'point' does not name a type
   99 | struct cmp_x { bool operator()(const point& pi, const point& pj) { return pi.x < pj.x; } };
      |                                      ^~~~~
a.cc:99:55: error: 'point' does not name a type
   99 | struct cmp_x { bool operator()(const point& pi, const point& pj) { return pi.x < pj.x; } };
      |                                                       ^~~~~
a.cc: In member function 'bool cmp_x::operator()(const int&, const int&)':
a.cc:99:78: error: request for member 'x' in 'pi', which is of non-class type 'const int'
   99 | struct cmp_x { bool operator()(const point& pi, const point& pj) { return pi.x < pj.x; } };
      |                                                                              ^
a.cc:99:85: error: request for member 'x' in 'pj', which is of non-class type 'const int'
   99 | struct cmp_x { bool operator()(const point& pi, const point& pj) { return pi.x < pj.x; } };
      |                                                                                     ^
a.cc: At global scope:
a.cc:100:38: error: 'point' does not name a type
  100 | struct cmp_y { bool operator()(const point& pi, const point& pj) { return pi.y < pj.y; } };
      |                                      ^~~~~
a.cc:100:55: error: 'point' does not name a type
  100 | struct cmp_y { bool operator()(const point& pi, const point& pj) { return pi.y < pj.y; } };
      |                                                       ^~~~~
a.cc: In member function 'bool cmp_y::operator()(const int&, const int&)':
a.cc:100:78: error: request for member 'y' in 'pi', which is of non-class type 'const int'
  100 | struct cmp_y { bool operator()(const point& pi, const point& pj) { return pi.y < pj.y; } };
      |                                                                              ^
a.cc:100:85: error: request for member 'y' in 'pj', which is of non-class type 'const int'
  100 | struct cmp_y { bool operator()(const point& pi, const point& pj) { return pi.y < pj.y; } };
      |                                                                                     ^
a.cc: At global scope:
a.cc:108:20: error: 'point' does not name a type
  108 | using vector_t   = point;
      |                    ^~~~~
a.cc:109:32: error: 'point' was not declared in this scope
  109 | using polygon_t  = std::vector<point>;
      |                                ^~~~~
a.cc:109:37: error: template argument 1 is invalid
  109 | using polygon_t  = std::vector<point>;
      |                                     ^
a.cc:109:37: error: template argument 2 is invalid
a.cc:110:32: error: 'segment' was not declared in this scope
  110 | using segments_t = std::vector<segment>;
      |                                ^~~~~~~
a.cc:110:39: error: template argument 1 is invalid
  110 | using segments_t = std::vector<segment>;
      |                                       ^
a.cc:110:39: error: template argument 2 is invalid
a.cc:124:18: error: 'coord_t' does not name a type
  124 | static constexpr coord_t det(const vector_t& a, const vector_t& b)
      |                  ^~~~~~~
a.cc:136:18: error: 'coord_t' does not name a type
  136 | static constexpr coord_t cross(const vector_t& a, const vector_t& b)
      |                  ^~~~~~~
a.cc:149:18: error: 'coord_t' does not name a type
  149 | static constexpr coord_t dot(const vector_t& a, const vector_t& b)
      |                  ^~~~~~~
a.cc:160:18: error: 'coord_t' does not name a type
  160 | static constexpr coord_t abs2(const vector_t& v)
      |                  ^~~~~~~
a.cc:172:15: error: 'coord_t' does not name a type
  172 | static inline coord_t abs(const vector_t& v)
      |               ^~~~~~~
a.cc:184:15: error: 'point' does not name a type
  184 | static inline point proj(const segment& s, const point& p)
      |               ^~~~~
a.cc:199:15: error: 'point' does not name a type
  199 | static inline point reflect(const segment& s, const point p)
      |               ^~~~~
a.cc:208:59: error: 'coord_t' was not declared in this scope
  208 | static inline bool approximate_combined_tolerance_compare(coord_t x, coord_t y) noexcept
      |                                                           ^~~~~~~
a.cc:208:70: error: 'coord_t' was not declared in this scope
  208 | static inline bool approximate_combined_tolerance_compare(coord_t x, coord_t y) noexcept
      |                                                                      ^~~~~~~
a.cc:208:79: error: expression list treated as compound expression in initializer [-fpermissive]
  208 | static inline bool approximate_combined_tolerance_compare(coord_t x, coord_t y) noexcept
      |                                                                               ^
a.cc:217:23: error: 'coord_t' was not declared in this scope
  217 | static inline bool eq(coord_t x, coord_t y)
      |                       ^~~~~~~
a.cc:217:34: error: 'coord_t' was not declared in this scope
  217 | static inline bool eq(coord_t x, coord_t y)
      |                                  ^~~~~~~
a.cc:217:43: error: expression list treated as compound expression in initializer [-fpermissive]
  217 | static inline bool eq(coord_t x, coord_t y)
      |                                           ^
a.cc:226:39: error: 'point' does not name a type
  226 | struct cmp_xy { bool operator()(const point& pi, const point& pj) { return pi.x < pj.x || (eq(pi.x, pj.x) && pi.y < pj.y); } };
      |                                       ^~~~~
a.cc:226:56: error: 'point' does not name a type
  226 | struct cmp_xy { bool operator()(const point& pi, const point& pj) { return pi.x < pj.x || (eq(pi.x, pj.x) && pi.y < pj.y); } };
      |                                                        ^~~~~
a.cc: In member function 'bool cmp_xy::operator()(const int&, const int&)':
a.cc:226:79: error: request for member 'x' in 'pi', which is of non-class type 'const int'
  226 | struct cmp_xy { bool operator()(const point& pi, const point& pj) { return pi.x < pj.x || (eq(pi.x, pj.x) && pi.y < pj.y); } };
      |                                                                               ^
a.cc:226:86: error: request for member 'x' in 'pj', which is of non-class type 'const int'
  226 | struct cmp_xy { bool operator()(const point& pi, const point& pj) { return pi.x < pj.x || (eq(pi.x, pj.x) && pi.y < pj.y); } };
      |                                                                                      ^
a.cc:226:98: error: request for member 'x' in 'pi', which is of non-class type 'const int'
  226 | struct cmp_xy { bool operator()(const point& pi, const point& pj) { return pi.x < pj.x || (eq(pi.x, pj.x) && pi.y < pj.y); } };
      |                                                                                                  ^
a.cc:226:104: error: request for member 'x' in 'pj', which is of non-class type 'const int'
  226 | struct cmp_xy { bool operator()(const point& pi, const point& pj) { return pi.x < pj.x || (eq(pi.x, pj.x) && pi.y < pj.y); } };
      |                                                                                                        ^
a.cc:226:105: error: 'eq' cannot be used as a function
  226 | struct cmp_xy { bool operator()(const point& pi, const point& pj) { return pi.x < pj.x || (eq(pi.x, pj.x) && pi.y < pj.y); } };
      |                                                                                                         ^
a.cc:226:113: error: request for member 'y' in 'pi', which is of non-class type 'const int'
  226 | struct cmp_xy { bool operator()(const point& pi, const point& pj) { return pi.x < pj.x || (eq(pi.x, pj.x) && pi.y < pj.y); } };
      |                                                                                                                 ^
a.cc:226:120: error: request for member 'y' in 'pj', which is of non-class type 'const int'
  226 | struct cmp_xy { bool operator()(const point& pi, const point& pj) { return pi.x < pj.x || (eq(pi.x, pj.x) && pi.y < pj.y); } };
      |                                                                                                                        ^
a.cc: At global scope:
a.cc:233:23: error: 'point' was not declared in this scope
  233 | static inline ffd ccw(point p0, point p1, point p2)
      |                       ^~~~~
a.cc:233:33: error: 'point' was not declared in this scope
  233 | static inline ffd ccw(point p0, point p1, point p2)
      |                                 ^~~~~
a.cc:233:43: error: 'point' was not declared in this scope
  233 | static inline ffd ccw(point p0, point p1, point p2)
      |                                           ^~~~~
a.cc:233:51: error: expression list treated as compound expression in initializer [-fpermissive]
  233 | static inline ffd ccw(point p0, point p1, point p2)
      |                                                   ^
a.cc:264:1: error: 'polygon_t' does not name a type
  264 | polygon_t andrew_scan(polygon_t& P, bool degenerate)
      | ^~~~~~~~~
a.cc: In function 'int main()':
a.cc:310:5: error: 'polygon_t' was not declared in this scope
  310 |     polygon_t poly(n);
      |     ^~~~~~~~~
a.cc:312:9: error: 'coord_t' was not declared in this scope
  312 |         coord_t x, y;
      |         ^~~~~~~
a.cc:313:16: error: 'x' was not declared in this scope
  313 |         cin >> x >> y;
      |                ^
a.cc:313:21: error: 'y' was not declared in this scope
  313 |         cin >> x >> y;
      |                     ^
a.cc:314:9: error: 'poly' was not declared in this scope
  314 |         poly[i] = point(x, y);
      |         ^~~~
a.cc:314:19: error: 'point' was not declared in this scope
  314 |         poly[i] = point(x, y);
      |                   ^~~~~
a.cc:317:14: error: expected ';' before 'convex_hull'
  317 |     polygon_t convex_hull = andrew_scan(poly, false);
      |              ^~~~~~~~~~~~
      |              ;
a.cc:319:5: error: 'index_t' was not declared in this scope
  319 |     index_t m = convex_hull.size();
      |     ^~~~~~~
a.cc:320:13: error: 'm' was not declared in this scope
  320 |     cout << m << endl;
      |             ^
a.cc:322:12: error: expected ';' before 'min_x'
  322 |