2699번: 격자점 컨벡스헐 ↗

#include <bits/stdc++.h>

#define for1(s,n) for(int i = s; i<n; i++)
#define for1j(s,n) for(int j = s; j<n; j++)
#define foreach(k) for(auto i : k)
#define foreachj(k) for(auto j : k)
#define pb(a) push_back((a))
#define sz(a) a.size()

using namespace std;
typedef unsigned long long ull;
typedef long long ll;
typedef vector <int> iv1;
typedef vector <vector<int> > iv2;
typedef vector <ll> llv1;
typedef unsigned int uint;
typedef vector <ull> ullv1;
typedef vector <vector <ull> > ullv2;

struct point{
  ll x, y, p=0, q=0;
};

ll N, M, tc;
vector <point> ar;

ll ccw(point p1, point p2, point p3) {
  ll ret = 1ll * (p1.x * p2.y + p2.x * p3.y + p3.x * p1.y - p2.x * p1.y - p3.x * p2.y - p1.x * p3.y);
  return ret > 0 ? 1 : (ret < 0 ? -1 : 0);
}

bool comp(point a, point b) {
  if(a.q * b.p != a.p*b.q) return 1ll * a.q * b.p > a.p * b.q;
  if(a.y != b.y) return a.y > b.y;
  return a.x < b.x;
}

void swapPoint(point a, point b) {
  point tmp;
  tmp = a;
  a = b;
  b= tmp;
}

vector <int> getConvexHull(vector <point>& points) {
  vector <int> stk; stk.clear();

  sort(points.begin(), points.end(), comp);

  // 0번째 점을 기준으로 상대 위치 계산
  for(int x=1; x<points.size(); x++) {
      points[x].p = points[x].x - points[0].x;
      points[x].q = points[x].y - points[0].y;
  }

  if(points.size() == 1) {
    return {0};
  }

  sort(points.begin() + 1, points.end(), comp);

  stk.push_back(0);
  stk.push_back(1);

  for(int next = 2; next < points.size(); next++) {
    while(stk.size() >= 2) {
      int second = stk.back(); stk.pop_back();
      int first = stk.back();
      
      if(ccw(points[first], points[second], points[next]) < 0) {
        stk.push_back(second);
        break;
      }
    }
    stk.push_back(next);
  }

  return stk;
}

void init() {
  ll x, y;

  cin >> N;

  ar.clear();

  for1(0, N) {
    cin >> x >> y;
    ar.push_back({ x, y, 0, 0});
  }
}

int main() {
  ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);

  cin >> tc;

  while(tc--) {
    init();

    vector <int> convex_hull = getConvexHull(ar);
    
    cout << convex_hull.size() << "\n";
    for(int i : convex_hull) {
      cout << ar[i].x << " " << ar[i].y << "\n";
    }
  }
}