#include<bits/stdc++.h> #define up(i,l,r) for(int i=(l);i<=(r);++i) #define down(i,l,r) for(int i=(l);i>=(r);--i) #define pi pair<int,int> #define p1 first #define p2 second #define m_p make_pair #define p_b push_back #define ppc __builtin_popcount using namespace std; typedef __int128 ll; const int maxn=2e5+10; const double eps=1e-7; inline ll read(){ ll x=0;short t=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')t=-1;ch=getchar();} while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar(); return x*t; } struct nd { ll x,y;int id; nd(){} nd(ll _x,ll _y){x=_x,y=_y;} nd(ll _x,ll _y,int _id){x=_x,y=_y,id=_id;} }; bool operator<(nd a,nd b){ if(a.x!=b.x)return a.x<b.x; return a.y<b.y; } bool operator==(nd a,nd b){return !(a<b||b<a);} struct e { nd a,b; e(){} e(nd _a,nd _b){a=_a,b=_b;} }; struct Tuple { nd i,j,k; Tuple(){} Tuple(nd _i,nd _j,nd _k){i=_i,j=_j,k=_k;} }; ll gcd(ll a,ll b){return ((!b)?a:gcd(b,a%b));} struct frc { ll a,b;frc(){} frc(ll _a,ll _b){a=_a,b=_b;if(b<0)a=-a,b=-b;ll g=gcd((a>0)?a:-a,b);a/=g,b/=g;} };bool operator<(frc a,frc b){ return a.a*b.b<b.a*a.b; } bool operator==(frc a,frc b){ return a.a==b.a&&a.b==b.b; } bool operator!=(frc a,frc b){ return !(a==b); } frc operator+(frc a,frc b){ return frc(a.a*b.b+b.a*a.b,a.b*b.b); } frc operator-(frc a,frc b){return a+frc(-b.a,b.b);} frc operator*(frc a,ll b){return frc(a.a*b,a.b);} frc operator*(frc a,frc b){return frc(a.a*b.a,a.b*b.b);} frc operator/(frc a,frc b){return a*frc(b.b,b.a);} int check(e a,e b){ if(b.a.x==b.b.x)swap(a,b); if(a.a.x==a.b.x){ if(a.a.y>a.b.y)swap(a.a,a.b); if(b.a.x==b.b.x){ if(a.a.x==b.a.x);else return 1; if(b.a.y>b.b.y)swap(b.a,b.b); if(a.b.y<=b.a.y)return 1; if(b.b.y<=a.a.y)return 1; return 0; } if(b.a.x>b.b.x)swap(b.a,b.b); frc kb(b.a.y-b.b.y,b.a.x-b.b.x),bb=frc(b.a.y,1)-(kb*b.a.x); frc v=(kb*a.a.x)+bb; if(b.a.x==a.a.x||b.b.x==a.a.x)return 1; if(frc(a.a.y,1)<v&&v<frc(a.b.y,1))return 0; return 1; } frc ka(a.a.y-a.b.y,a.a.x-a.b.x),kb(b.a.y-b.b.y,b.a.x-b.b.x); frc ba=frc(a.a.y,1)-(ka*a.a.x),bb=frc(b.a.y,1)-(kb*b.a.x); if(ka==kb){ if(ba==bb){ if(a.a.x>a.b.x)swap(a.a,a.b); if(b.a.x>b.b.x)swap(b.a,b.b); if(a.b.x<=b.a.x||b.b.x<=a.a.x)return 1; return 0; } return 1; } #define ck(x) ((ka*x+ba)==(kb*x+bb)) #define ck1(x) ((ka*x+ba)<(kb*x+bb)) if(ck(a.a.x)||ck(a.b.x)||ck(b.a.x)||ck(b.b.x))return 1; if(a.a.x>a.b.x)swap(a.a,a.b); if(b.a.x>b.b.x)swap(b.a,b.b); if(max(a.a.x,b.a.x)>=min(a.b.x,b.b.x))return 1; return !(ck1(max(a.a.x,b.a.x))^ck1(min(a.b.x,b.b.x))); } ll cross(nd a,nd b,nd c){ b.x-=a.x,b.y-=a.y,c.x-=a.x,c.y-=a.y; return b.x*c.y-c.x*b.y; } ll dist(nd a,nd b){ return (b.x-a.x)*(b.x-a.x)+(b.y-a.y)*(b.y-a.y); } nd cmp1(nd a,nd b,nd c){ return cross(a,b,c)?(cross(a,b,c)>0?b:c):((dist(a,b)<dist(a,c))?b:c); } nd cmp2(nd a,nd b,nd c){ return cross(a,b,c)?(cross(a,b,c)<0?b:c):((dist(a,b)<dist(a,c))?b:c); } nd get(nd x,nd u,vector<nd>S){ nd P,Q;bool f=0; for(auto it:S){ if(it.id==u.id||it.id==x.id)continue; if(!f)P=Q=it,f=1; else P=cmp1(u,P,it),Q=cmp2(u,Q,it); } //cout<<P.id<<" "<<Q.id<<" "<<S.size()<<endl; if(cross(x,u,P)<0)return P; if(cross(x,u,Q)>0)return Q; return nd(-1,-1,-1); } bool chk(Tuple a,Tuple b){ for(e X:{e(a.i,a.j),e(a.i,a.k),e(a.j,a.k)}){ for(e Y:{e(b.i,b.j),e(b.i,b.k),e(b.j,b.k)}){ if(!check(X,Y))return 0; } }return 1; } int T; void slv(){ vector<Tuple>ve; int n=read();vector<nd>v; up(i,1,n){ int x=read(),y=read(); v.p_b((nd){x,y,i}); }sort(v.begin(),v.end()); while((int)v.size()>=3){ nd P=v[0],Q=v[1],U=get(P,Q,v); //cout<<P.id<<" "<<Q.id<<" "<<U.id<<endl; if(U.id==-1)break; v.erase(find(v.begin(),v.end(),P)); v.erase(find(v.begin(),v.end(),Q)); v.erase(find(v.begin(),v.end(),U)); ve.p_b(Tuple(P,Q,U)); } if((int)v.size()>=3){ while(v.size()%3)v.pop_back(); vector<nd>L,R; while((!ve.empty())&&(L.size()+R.size())*2<v.size()){ auto x=ve.back();ve.pop_back(); for(auto k:{x.i,x.j,x.k}){ if(!cross(v[0],v[1],k))v.p_b(k); else if(cross(v[0],v[1],k)>0)L.p_b(k); else R.p_b(k); } } while(v.size()>(L.size()+R.size())*2)v.pop_back(); int sz=(v.size()==(L.size()+R.size())*2)?0:3; sort(v.begin(),v.end()); reverse(v.begin(),v.end()); while(v.size()>sz){ nd a=v.back();v.pop_back(); nd b=v.back();v.pop_back(); if(L.empty())L=R,R.clear(); if(L.size()){ nd p=get(a,b,L); L.erase(find(L.begin(),L.end(),p)); ve.p_b(Tuple(a,b,p)); }else {v.p_b(a),v.p_b(b);break;} } if(v.size()){ reverse(v.begin(),v.end()); for(nd x:L)v.p_b(x); for(nd x:R)v.p_b(x); bool ok=0; up(i,0,5){ up(j,i+1,5){ up(k,j+1,5){ int p=0,q=0,r=0; while(p==i||p==j||p==k)p++;q=p+1; while(q==i||q==j||q==k)q++;r=q+1; while(r==i||r==j||r==k)r++; if(!cross(v[i],v[j],v[k]))continue; if(!cross(v[p],v[q],v[r]))continue; if(chk(Tuple(v[i],v[j],v[k]),Tuple(v[p],v[q],v[r]))){ ve.p_b(Tuple(v[i],v[j],v[k])); ve.p_b(Tuple(v[p],v[q],v[r])); ok=1;break; } }if(ok)break; }if(ok)break; } } } printf("Case #%d: %d\n",++T,(int)ve.size()); for(auto it:ve)printf("%d %d %d\n",it.i.id,it.j.id,it.k.id); } int main(){ //freopen("1.in","r",stdin),freopen("1.out","w",stdout); int t=read();while(t--)slv(); //slv(); //cerr<<clock()*1.0/CLOCKS_PER_SEC<<"s\n"; return 0; }