#include <algorithm>
#include <cmath>
#include <cstdint>
#include <iostream>
#include <utility>
#include <vector>
using namespace std;
struct Point {
long long x;
long long y;
};
using i128 = __int128_t;
static i128 cross(const Point& a, const Point& b, const Point& c) {
return (i128)(b.x - a.x) * (c.y - a.y) - (i128)(b.y - a.y) * (c.x - a.x);
}
struct PolarRay {
long double angle;
int id;
};
static vector<int> convex_hull(const vector<int>& ids, const vector<Point>& pts) {
vector<int> order = ids;
sort(order.begin(), order.end(), [&](int lhs, int rhs) {
if (pts[lhs].x != pts[rhs].x) {
return pts[lhs].x < pts[rhs].x;
}
return pts[lhs].y < pts[rhs].y;
});
if (order.size() <= 1) {
return order;
}
vector<int> lower;
for (int id : order) {
while (lower.size() >= 2 &&
cross(pts[lower[lower.size() - 2]], pts[lower.back()], pts[id]) <= 0) {
lower.pop_back();
}
lower.push_back(id);
}
vector<int> upper;
for (int i = static_cast<int>(order.size()) - 1; i >= 0; --i) {
int id = order[i];
while (upper.size() >= 2 &&
cross(pts[upper[upper.size() - 2]], pts[upper.back()], pts[id]) <= 0) {
upper.pop_back();
}
upper.push_back(id);
}
lower.pop_back();
upper.pop_back();
lower.insert(lower.end(), upper.begin(), upper.end());
return lower;
}
static vector<vector<int>> build_petals(const vector<int>& ids, int pivot, const vector<Point>& pts) {
const long double PI = acosl(-1.0L);
const long double TAU = 2.0L * PI;
const long double EPS = 1e-18L;
vector<PolarRay> rays;
vector<long double> cuts;
rays.reserve(ids.size() - 1);
cuts.reserve(ids.size() - 1);
const Point& p = pts[pivot];
for (int id : ids) {
if (id == pivot) {
continue;
}
long double angle = atan2l((long double)pts[id].y - p.y, (long double)pts[id].x - p.x);
if (angle < 0) {
angle += TAU;
}
long double opposite = angle + PI;
if (opposite >= TAU) {
opposite -= TAU;
}
rays.push_back({angle, id});
cuts.push_back(opposite);
}
sort(rays.begin(), rays.end(), [](const PolarRay& lhs, const PolarRay& rhs) {
return lhs.angle < rhs.angle;
});
sort(cuts.begin(), cuts.end());
const int m = static_cast<int>(rays.size());
vector<long double> extended_cuts = cuts;
extended_cuts.reserve(2 * m);
for (long double cut : cuts) {
extended_cuts.push_back(cut + TAU);
}
vector<bool> separated(m, false);
int cut_ptr = 0;
for (int i = 0; i < m; ++i) {
const long double left = rays[i].angle;
const long double right = rays[(i + 1) % m].angle + (i + 1 == m ? TAU : 0.0L);
while (cut_ptr < (int)extended_cuts.size() && extended_cuts[cut_ptr] <= left + EPS) {
++cut_ptr;
}
separated[i] = cut_ptr < (int)extended_cuts.size() && extended_cuts[cut_ptr] < right - EPS;
}
if (none_of(separated.begin(), separated.end(), [](bool value) { return value; })) {
vector<int> all;
all.reserve(m);
for (const auto& ray : rays) {
all.push_back(ray.id);
}
return {all};
}
int start_gap = 0;
while (!separated[start_gap]) {
++start_gap;
}
vector<vector<int>> groups;
vector<int> current;
for (int step = 0; step < m; ++step) {
const int idx = (start_gap + 1 + step) % m;
current.push_back(rays[idx].id);
if (separated[idx]) {
groups.push_back(current);
current.clear();
}
}
if (!current.empty()) {
groups.push_back(current);
}
return groups;
}
static vector<pair<int, int>> solve_subproblem(const vector<int>& ids, const vector<Point>& pts) {
if (ids.size() == 2) {
return {{ids[0], ids[1]}};
}
const vector<int> hull = convex_hull(ids, pts);
if (hull.size() == ids.size()) {
vector<pair<int, int>> edges;
edges.reserve(ids.size());
for (int i = 0; i < (int)hull.size(); ++i) {
edges.push_back({hull[i], hull[(i + 1) % hull.size()]});
}
return edges;
}
vector<char> on_hull(pts.size(), false);
for (int id : hull) {
on_hull[id] = true;
}
int pivot = -1;
for (int id : ids) {
if (!on_hull[id]) {
pivot = id;
break;
}
}
vector<vector<int>> groups = build_petals(ids, pivot, pts);
const bool all_singletons = all_of(groups.begin(), groups.end(), [](const vector<int>& group) {
return group.size() == 1;
});
if (all_singletons) {
vector<pair<int, int>> edges;
edges.reserve(groups.size());
for (const auto& group : groups) {
edges.push_back({pivot, group[0]});
}
return edges;
}
vector<pair<int, int>> edges;
for (const auto& group : groups) {
vector<int> next_ids;
next_ids.reserve(group.size() + 1);
next_ids.push_back(pivot);
next_ids.insert(next_ids.end(), group.begin(), group.end());
vector<pair<int, int>> sub_edges = solve_subproblem(next_ids, pts);
edges.insert(edges.end(), sub_edges.begin(), sub_edges.end());
}
return edges;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n;
cin >> n;
vector<Point> pts(n + 1);
for (int i = 1; i <= n; ++i) {
cin >> pts[i].x >> pts[i].y;
}
vector<int> ids(n);
for (int i = 0; i < n; ++i) {
ids[i] = i + 1;
}
vector<pair<int, int>> edges = solve_subproblem(ids, pts);
cout << edges.size() << '\n';
for (auto [u, v] : edges) {
cout << u << ' ' << v << '\n';
}
return 0;
}
