Untitled

#include<bits/stdc++.h>
using namespace std;

struct Point {
  int x, y;
  void in(){
    cin >> x >> y;
  }
};

const int inf = 1e9;

int n;
// x[1][0] <-> x1-, x[1][1] <-> x1+ ...
int x[5][2], y[5][2];
// Chỉ số của các tọa độ v1-, v1+ ... trong mảng 
int indexV[5][2]; 
vector<int> I[5];
vector<int> L[5];
vector<Point> arr;


void input(){
  cin >> n;
  Point c;
  arr.push_back(c);
  for (int i = 0; i < n; i++){
    c.in(); 
    arr.push_back(c);
  }
}

// sai o diem tim v3
void find_v(){
  vector<vector<int>> J(5, vector<int>(1, 1));
  int xmin = arr[1].x;
  int xmax = arr[1].x;
  int ymin = arr[1].y;
  int ymax = arr[1].y;
  for (int i = 2; i <= n; i++){

    if (arr[i].y == ymin){
      J[1].push_back(i);
    }

    if (arr[i].y < ymin){
      J[1].clear();
      J[1].push_back(i);
      ymin = arr[i].y;
    }

    if (arr[i].x == xmax){
      J[2].push_back(i);
    }

    if (arr[i].x > xmax){
      J[2].clear();
      J[2].push_back(i);
      xmax = arr[i].x;
    }

    if (arr[i].y == ymax){
      J[3].push_back(i);
    }

    if (arr[i].y > ymax){
      J[3].clear();
      J[3].push_back(i);
      ymax = arr[i].y;
    }

    if (arr[i].x == xmin){
      J[4].push_back(i);
    }

    if (arr[i].x < xmin){
      J[4].clear();
      J[4].push_back(i);
      xmin = arr[i].x;
    }
  }

  // ALO (9)
  y[1][0] = ymin;
  y[1][1] = ymin;
  x[2][0] = xmax;
  x[2][1] = xmax;
  y[3][0] = ymax;
  y[3][1] = ymax;
  x[4][0] = xmin;
  x[4][1] = xmin;

  x[1][0] = inf;
  x[1][1] = -inf;
  for (int i : J[1]) x[1][0] = min(x[1][0], arr[i].x);
  for (int i : J[1]) x[1][1] = max(x[1][1], arr[i].x);

  y[2][0] = inf;
  y[2][1] = -inf;
  for (int i : J[2]) y[2][0] = min(y[2][0], arr[i].y);
  for (int i : J[2]) y[2][1] = max(y[2][1], arr[i].y);

  x[3][0] = -inf;
  x[3][1] = inf;
  for (int i : J[3]) x[3][0] = max(x[3][0], arr[i].x);
  for (int i : J[3]) x[3][1] = min(x[3][1], arr[i].x);

  y[4][0] = -inf;
  y[4][1] = inf;
  for (int i : J[4]) y[4][0] = max(y[4][0], arr[i].y);
  for (int i : J[4]) y[4][1] = min(y[4][1], arr[i].y);

  //Đánh chỉ số lại các tọa độ điểm, v1- tương ứng điểm đầu tiên 
  vector<Point> arr2;
  arr2 = arr;
  int p;
  for (int i = 1; i <= n; i++){
    if (arr[i].x == x[1][0] && arr[i].y == y[1][0]){
      p = i; break;
    }
  }
  // p chỉ số của của v1- trong mảng ban đầu
  // thực hiện dịch v1- thành điểm đầu tiên
  for (int i = 1; i <= n; i++){
    if (i <= n + 1 - p) arr[i] = arr2[i + p - 1];
    else arr[i] = arr2[i + p - 1 - n];
    // lưu chỉ số của các tọa độ v-+
    for (int k = 1; k <= 4; k++){
      if (arr[i].x == x[k][0] && arr[i].y == y[k][0]){
        indexV[k][0] = i;
      }
      if (arr[i].x == x[k][1] && arr[i].y == y[k][1]){
        indexV[k][1] = i;
      }
    }
  }
}

void find_I(){
  for (int i = 1; i <= n; i++){
    int curX = arr[i].x;
    int curY = arr[i].y;
    int preX = arr[i - 1].x;
    int preY = arr[i - 1].y;
    if (indexV[1][1] < i && i < indexV[2][0] && curX > preX && curY == preY && curY < y[2][0]) I[1].push_back(i);
    if (indexV[2][1] < i && i < indexV[3][0] && curY > preY && curX == preX && curX > x[3][0]) I[2].push_back(i);
    if (indexV[3][1] < i && i < indexV[4][0] && curX < preX && curY == preY && curY > y[4][0]) I[3].push_back(i);
    if (indexV[4][1] < i && i <= n && curY < preY && curX == preX && curX < arr[1].x) I[4].push_back(i);
  }
}
// I*
void find_L_1(){
  // 1+ = 2-
  L[1].push_back(indexV[1][1]);
  if (indexV[1][1] == indexV[2][0]) return;
  vector<int> nL;
  int i_ = indexV[1][1];

  while(true){
    nL.clear();
    for (int i : I[1]){
      if (arr[i].x > arr[i_].x) nL.push_back(i);
    }
    if ((int)nL.size() == 0){
      L[1].push_back(indexV[2][0]); break;
    }

    // tìm y min trong tập hợp nL
    int y_ = inf;
    for (int i : nL) y_ = min(y_, arr[i].y);
    // cập nhật i_ là chỉ số lớn nhât có giá trị = y_
    for (int i : nL) if (arr[i].y == y_) i_ = i;
    L[1].push_back(i_);
    // cập nhật lại I1
    I[1].clear();
    for (int i : nL) if (i > i_) I[1].push_back(i);
  }
}

void find_L_2(){
  L[2].push_back(indexV[2][1]);
  if (indexV[2][1] == indexV[3][0]) return;
  vector<int> nL;
  int i_ = indexV[2][1];

  while(true){
    nL.clear();
    for (int i : I[2]){
      if (arr[i].y > arr[i_].y) nL.push_back(i);
    }
    if ((int)nL.size() == 0){
      L[2].push_back(indexV[3][0]); break;
    }

    // tìm x max trong tập hợp nL
    int x_ = -inf;
    for (int i : nL) x_ = max(x_, arr[i].x);
    // cập nhật i_ là chỉ số lớn nhât có giá trị x = x_
    for (int i : nL) if (arr[i].x == x_) i_ = i;
    L[2].push_back(i_);
    // cập nhật lại I2
    I[2].clear();
    for (int i : nL) if (i > i_) I[2].push_back(i);
  }
}

void find_L_3(){
  L[3].push_back(indexV[3][1]);
  if (indexV[3][1] == indexV[4][0]) return;
  vector<int> nL;
  int i_ = indexV[3][1];

  while(true){
    nL.clear();
    for (int i : I[3]){
      if (arr[i].x < arr[i_].x) nL.push_back(i);
    }
    if ((int)nL.size() == 0){
      L[3].push_back(indexV[4][0]); break;
    }

    // tìm y max trong tập hợp nL
    int y_ = -inf;
    for (int i : nL) y_ = max(y_, arr[i].y);
    // cập nhật i_ là chỉ số lớn nhât có giá trị y = y_
    for (int i : nL) if (arr[i].y == y_) i_ = i;
    L[3].push_back(i_);
    // cập nhật lại I1
    I[3].clear();
    for (int i : nL) if (i > i_) I[3].push_back(i);
  }
}

void find_L_4(){
  if (indexV[4][1] == 1){
    L[4].push_back(1);
    return;
  }

  L[4].push_back(indexV[4][1]);
  vector<int> nL;
  int i_ = indexV[4][1];

  while(true){
    nL.clear();
    for (int i : I[4]){
      if (arr[i].y < arr[i_].y) nL.push_back(i);
    }
    if ((int)nL.size() == 0){
      L[4].push_back(1); break;
    }

    // tìm x min trong tập hợp nL
    int x_ = inf;
    for (int i : nL) x_ = min(x_, arr[i].x);
    // cập nhật i_ là chỉ số lớn nhât có giá trị x = x_
    for (int i : nL) if (arr[i].x == x_) i_ = i;
    L[4].push_back(i_);
    // cập nhật lại I2
    I[4].clear();
    for (int i : nL) if (i > i_) I[4].push_back(i);
  }
}

void print(){
  cout << "Toa do bao loi: " << '\n';
  for (int k = 1; k <= 4; k++){
    for (int i = 0; i < (int)L[k].size(); i++){
      int p_cur = L[k][i];
      if (i > 0){
        int p_pre = L[k][i - 1];
        if (k == 1 || k == 3) cout << arr[p_pre].x << ' ' << arr[p_cur].y << '\n';
        if (k == 2 || k == 4) cout << arr[p_cur].x << ' ' << arr[p_pre].y << '\n';
      }
      cout << arr[p_cur].x << ' ' << arr[p_cur].y << '\n'; 
    }
  }
}


int32_t main(){
  ios_base::sync_with_stdio(false), cin.tie(0);
  input();
  find_v();
  find_I();
  find_L_1();
  find_L_2();
  find_L_3();
  find_L_4();
  print();

}