这篇题解只讲怎么做，正确性证明留给后人吧。

写一个 work(S) 函数表示你现在要处理点集 $S$。

先找出点集 $S$ 的凸包。

如果凸包就是整个 $S$ 那就把这个凸包连出来然后直接 return。

否则在凸包内部随便选一个点，和点集 $S$ 中的其他点连边（并延长成为直线），这些直线会将平面分成若干部分，把这些部分中有点的情况递归下去即可。

代码：差不多就是贺了一遍 @Milmon 写的。

#include<bits/stdc++.h>
using namespace std;
namespace gza{
	#define int long long
	#define pb push_back
	#define MT int TTT=R;while(TTT--)
	#define pc putchar
	#define R read()
	#define fo(i,a,b) for(int i=a;i<=b;i++)
	#define rep(i,a,b) for(int i=a;i>=b;i--)
	#define m1(a,b) memset(a,b,sizeof a)
	namespace IO
	{
		inline int read()
		{
		    int x=0;
		    char ch=getchar();
		    bool f=0;
		    while(!isdigit(ch)){if(ch=='-') f=1;ch=getchar();}
		    while(isdigit(ch)) x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
		    if(f) x=-x;
		    return x;    
		}
		template<typename T> inline void write(T x)
		{
		    if(x<0) pc('-'),x=-x;
		    if(x>9) write(x/10);
		    pc(x%10+'0');
		}
	};
	namespace math
	{
		inline int gcd(int a,int b)
		{
			int az=__builtin_ctz(a),bz=__builtin_ctz(b),z=(az>bz)?bz:az,t;
		    b>>=bz;
		    while(a) a>>=az,t=a-b,b=a,az=__builtin_ctz(t<0?-t:t),a=t<0?-t:t;
		    return b<<z;
		}
		inline int qmi(int a,int b,int p)
		{
			int res=1;
			while(b)
			{
				if(b&1) res=res*a%p;
				a=a*a%p;
				b>>=1;
			}
			return res;
		}
		const int MAXN=2e6+10;
		int my_fac[MAXN],my_inv[MAXN];
		void init_binom(int mod)
		{
			my_fac[0]=1;fo(i,1,min(MAXN,mod)-1) my_fac[i]=my_fac[i-1]*i%mod;
			my_inv[min(MAXN,mod)-1]=qmi(my_fac[min(MAXN,mod)-1],mod-2,mod);rep(i,min(MAXN,mod)-2,0) my_inv[i]=my_inv[i+1]*(i+1)%mod;
		}
		int binom(int a,int b,int mod)
		{
			return my_fac[a]*my_inv[b]%mod*my_inv[a-b]%mod;
		}
	};
	using namespace IO;
	using namespace math;
	
	const int N=2010;
	const double pi=acos(-1);
	#define PII pair<int,int>
	#define x first
	#define y second
	#define cp const PII&
	inline PII operator- (cp A,cp B){return {A.x-B.x,A.y-B.y};}
	inline int operator* (cp A,cp B){return A.x*B.y-A.y*B.x;}
	PII inf={2e9,2e9};
	vector<PII> ans;
	map<PII,int> id;
	void add(PII a,PII b){ans.pb({id[a],id[b]});}
	void work(vector<PII>& now)
	{
		vector<PII> up,down;
		int n=now.size();
		sort(now.begin(),now.end());
		for(auto& x:now)
		{
			while(up.size()>=2&&(up.back()-up.end()[-2])*(x-up.back())>=0) up.pop_back();
			while(down.size()>=2&&(down.back()-down.end()[-2])*(x-down.back())<=0) down.pop_back();
			up.pb(x),down.pb(x);
		}
		up.pop_back(),up.insert(up.end(),down.rbegin(),down.rend()),up.pop_back();
		if(up.size()==n) fo(i,(n==2),n-1) add(up[i],up[(i+1)%n]);
		else
		{
			set<PII> s;
			for(auto i:up) s.insert(i); 
			vector<pair<double,PII> > v;
			PII tmp;
			for(auto i:now) if(!s.count(i)){tmp=i;break;}
			for(auto i:now) if(i!=tmp)
			{
				double theta=atan2((i-tmp).y,(i-tmp).x);
				v.pb({theta,i});
				v.pb({theta>=0?theta-pi:theta+pi,inf});
			}
			sort(v.begin(),v.end());
			int p=0;
			while(v[p].second!=inf) p++;
			rotate(v.begin(),v.begin()+p+1,v.end());
			vector<PII> nex;
			for(auto i:v)
			{
				if(i.second!=inf) nex.pb(i.second);
				else if(!nex.empty()) nex.pb(tmp),work(nex),nex.clear();
			}
		}
	}
	void main(){
		int n=R;
		vector<PII> all;
		fo(i,1,n)
		{
			int x=R,y=R;
			all.pb({x,y});
			id[{x,y}]=i;
		}
		work(all);
		write(ans.size()),puts("");
		for(auto [x,y]:ans) write(x),pc(' '),write(y),puts("");
	}
}
signed main(){
	
	gza::main();
}