#include<bits/stdc++.h>
#define all(x) begin(x), end(x)
using namespace std;
using ll = long long;
vector<array<int, 2>> solve(int n, vector<array<int, 2>> pts) {
set<array<int, 2>> X, Y;
for(int i = 0; i < n; i++) {
X.insert({pts[i][0], i});
Y.insert({pts[i][1], i});
}
auto del = [&](int i) {
X.erase({pts[i][0], i});
Y.erase({pts[i][1], i});
};
auto find = [&](int mode) -> array<int, 2> {
array<int, 2> v;
if(mode == 0)
v = *Y.rbegin();
if(mode == 1)
v = *X.rbegin();
if(mode == 2)
v = *Y.begin();
if(mode == 3)
v = *X.begin();
del(v[1]);
return {pts[v[1]][0], pts[v[1]][1]};
};
vector<array<int, 2>> targets;
for(int i = 0; i < n; i++) {
targets.push_back(find(i%4));
}
vector<array<int, 2>> sol;
sol.push_back({0, targets[0][1]});
for(int i = 0; i+1 < n; i++) {
int mode = i%4;
if(mode == 0) {
int y = sol.back()[1];
if(targets[i][0] > targets[i+1][0])
sol.push_back({targets[i][0], y});
sol.push_back({targets[i+1][0], y});
}
if(mode == 2) {
int y = sol.back()[1];
if(targets[i][0] < targets[i+1][0])
sol.push_back({targets[i][0], y});
sol.push_back({targets[i+1][0], y});
}
if(mode == 3) {
int x = sol.back()[0];
if(targets[i][1] > targets[i+1][1])
sol.push_back({x, targets[i][1]});
sol.push_back({x, targets[i+1][1]});
}
if(mode == 1) {
int x = sol.back()[0];
if(targets[i][1] < targets[i+1][1])
sol.push_back({x, targets[i][1]});
sol.push_back({x, targets[i+1][1]});
}
//cerr << (i%4) << " " << targets[i][0] << " " << targets[i][1] << endl;
}
sol.push_back(targets.back());
return sol;
}
template<int inv>
vector<array<int, 2>> transform(vector<array<int, 2>> a, int rx, int ry, int sw) {
return a;
if(inv && sw) swap(rx, ry);
for(auto &[x, y] : a) {
if(rx) x *= -1;
if(ry) y *= -1;
if(sw) swap(x, y);
}
return a;
}
int main() {
cin.tie(0)->sync_with_stdio(0);
int n;
cin >> n;
vector<array<int, 2>> pts(n);
for(auto &[x, y] : pts) cin >> x >> y;
vector<array<int, 2>> sol = solve(n, pts);
for(int msk = 1; msk < 8; msk++) {
auto tmp = transform<1>(solve(n, transform<0>(pts, msk&1, msk&2, msk&4)), msk&1, msk&2, msk&4);
if(tmp.size() < sol.size()) sol = tmp;
}
cout << sol.size() << '\n';
for(auto [x, y] : sol) cout << x << " " << y << '\n';
}
Compilation message
/usr/bin/ld: /tmp/ccXtnz47.o: in function `main':
grader.cpp:(.text.startup+0x0): multiple definition of `main'; /tmp/ccxoS9T6.o:walk.cpp:(.text.startup+0x0): first defined here
/usr/bin/ld: /tmp/ccXtnz47.o: in function `main':
grader.cpp:(.text.startup+0x395): undefined reference to `min_distance(std::vector<int, std::allocator<int> >, std::vector<int, std::allocator<int> >, std::vector<int, std::allocator<int> >, std::vector<int, std::allocator<int> >, std::vector<int, std::allocator<int> >, int, int)'
collect2: error: ld returned 1 exit status
