#include <bits/stdc++.h>
#define ll long long
using namespace std;
struct point
{
ll x,y;
};
point base;
int area( point p, point q, point r )
{
ll x[]= {p.x, q.x, r.x};
ll y[]= {p.y, q.y, r.y};
ll a= 0;
int j= 2;
for(int i=0; i<3; i++)
{
a+=(x[j]+x[i])*(y[j]-y[i]);
j= i;
}
if(a>0)
return 1;
if(a<0)
return 2;
return 0;
}
bool cmp1( const point&a, const point&b )
{
if(a.y==b.y)
return a.x<b.x;
return a.y<b.y;
}
bool cmp2( const point&a, const point&b )
{
if( area( base, a, b )==2 )
return 1;
return 0;
}
void cHull( point points[], int n )
{
vector<point> hull;
int l= 0;
for(int i=1; i<n; i++)
if(points[i].y<points[l].y)
l= i;
int p=l, q;
do
{
vector <point> col;
hull.push_back( points[p] );
q= (p+1)%n;
for(int i=0; i<n; i++)
{
if(i==q or i==p)
continue;
int pos= area( points[p], points[q], points[i] );
if( pos==2 )
q= i;
else if(pos==0)
{
ll dist1= (points[p].x-points[i].x)*(points[p].x-points[i].x)
+(points[p].y-points[i].y)*(points[p].y-points[i].y);
ll dist2= (points[p].x-points[q].x)*(points[p].x-points[q].x)
+(points[p].y-points[q].y)*(points[p].y-points[q].y);
if(dist1>dist2)
{
col.push_back( points[q] );
q= i;
}
else
col.push_back(points[i]);
}
}
p= q;
for(int i=0;i<col.size();i++)
hull.push_back( col[i] );
}
while(points[p].x!=points[l].x or points[p].y!=points[l].y);
sort( hull.begin(), hull.end(), cmp1 );
base= hull[0];
sort( hull.begin()+1, hull.end(), cmp2 );
int sz= hull.size();
int cnt= 0;
for(int i=0; i<sz; i++)
{
if(hull[i].x==base.x and hull[i].y==base.y)
continue;
cnt++;
}
while(hull.size()<3)
hull.push_back(base);
cout<<max(cnt+2, 3)<<endl;
cout<<base.x<<" "<<base.y<<endl;
int k=0;
sz= hull.size();
for(int i=0; i<sz; i++)
{
//cout<<k<<endl;
if(hull[i].x==base.x and hull[i].y==base.y)
{
k++;
if(k<=2)
continue;
}
cout<<hull[i].x<<" "<<hull[i].y<<endl;
}
cout<<base.x<<" "<<base.y<<endl;
}
int main()
{
int tc;
cin>>tc;
cout<<tc<<endl;
for(int t=1; t<=tc; t++)
{
int n;
cin>>n;
point points[n];
for(int i=0; i<n; i++)
{
point p;
cin>>p.x>>p.y;
points[i]= p;
}
int l;
if(t!=tc)
cin>>l;
cHull(points, n);
if(t!=tc)
cout<<l<<endl;
}
}
I2luY2x1ZGUgPGJpdHMvc3RkYysrLmg+CiNkZWZpbmUgbGwgbG9uZyBsb25nCnVzaW5nIG5hbWVzcGFjZSBzdGQ7CgpzdHJ1Y3QgcG9pbnQKewogICAgbGwgeCx5Owp9OwoKcG9pbnQgYmFzZTsKCmludCBhcmVhKCBwb2ludCBwLCBwb2ludCBxLCBwb2ludCByICkKewogICAgbGwgeFtdPSB7cC54LCBxLngsIHIueH07CiAgICBsbCB5W109IHtwLnksIHEueSwgci55fTsKCiAgICBsbCBhPSAwOwogICAgaW50IGo9IDI7CgogICAgZm9yKGludCBpPTA7IGk8MzsgaSsrKQogICAgewogICAgICAgIGErPSh4W2pdK3hbaV0pKih5W2pdLXlbaV0pOwogICAgICAgIGo9IGk7CiAgICB9CgogICAgaWYoYT4wKQogICAgICAgIHJldHVybiAxOwogICAgaWYoYTwwKQogICAgICAgIHJldHVybiAyOwogICAgcmV0dXJuIDA7Cn0KCmJvb2wgY21wMSggY29uc3QgcG9pbnQmYSwgY29uc3QgcG9pbnQmYiAgKQp7CiAgICBpZihhLnk9PWIueSkKICAgICAgICByZXR1cm4gYS54PGIueDsKICAgIHJldHVybiBhLnk8Yi55Owp9Cgpib29sIGNtcDIoIGNvbnN0IHBvaW50JmEsIGNvbnN0IHBvaW50JmIgKQp7CiAgICBpZiggYXJlYSggYmFzZSwgYSwgYiApPT0yICkKICAgICAgICByZXR1cm4gMTsKICAgIHJldHVybiAwOwp9CgoKdm9pZCBjSHVsbCggcG9pbnQgcG9pbnRzW10sIGludCBuICkKewogICAgdmVjdG9yPHBvaW50PiBodWxsOwogICAgaW50IGw9IDA7CgogICAgZm9yKGludCBpPTE7IGk8bjsgaSsrKQogICAgICAgIGlmKHBvaW50c1tpXS55PHBvaW50c1tsXS55KQogICAgICAgICAgICBsPSBpOwoKICAgIGludCBwPWwsIHE7CgogICAgZG8KICAgIHsKICAgICAgICB2ZWN0b3IgPHBvaW50PiBjb2w7CgogICAgICAgIGh1bGwucHVzaF9iYWNrKCBwb2ludHNbcF0gKTsKICAgICAgICBxPSAocCsxKSVuOwoKICAgICAgICBmb3IoaW50IGk9MDsgaTxuOyBpKyspCiAgICAgICAgewogICAgICAgICAgICBpZihpPT1xIG9yIGk9PXApCiAgICAgICAgICAgICAgICBjb250aW51ZTsKICAgICAgICAgICAgaW50IHBvcz0gYXJlYSggcG9pbnRzW3BdLCBwb2ludHNbcV0sIHBvaW50c1tpXSApOwogICAgICAgICAgICBpZiggcG9zPT0yICkKICAgICAgICAgICAgICAgIHE9IGk7CiAgICAgICAgICAgIGVsc2UgaWYocG9zPT0wKQogICAgICAgICAgICB7CiAgICAgICAgICAgICAgICBsbCBkaXN0MT0gKHBvaW50c1twXS54LXBvaW50c1tpXS54KSoocG9pbnRzW3BdLngtcG9pbnRzW2ldLngpCiAgICAgICAgICAgICAgICAgICAgICAgICAgKyhwb2ludHNbcF0ueS1wb2ludHNbaV0ueSkqKHBvaW50c1twXS55LXBvaW50c1tpXS55KTsKICAgICAgICAgICAgICAgIGxsIGRpc3QyPSAocG9pbnRzW3BdLngtcG9pbnRzW3FdLngpKihwb2ludHNbcF0ueC1wb2ludHNbcV0ueCkKICAgICAgICAgICAgICAgICAgICAgICAgICArKHBvaW50c1twXS55LXBvaW50c1txXS55KSoocG9pbnRzW3BdLnktcG9pbnRzW3FdLnkpOwoKICAgICAgICAgICAgICAgIGlmKGRpc3QxPmRpc3QyKQogICAgICAgICAgICAgICAgewogICAgICAgICAgICAgICAgICAgIGNvbC5wdXNoX2JhY2soIHBvaW50c1txXSApOwogICAgICAgICAgICAgICAgICAgIHE9IGk7CiAgICAgICAgICAgICAgICB9CiAgICAgICAgICAgICAgICBlbHNlCiAgICAgICAgICAgICAgICAgICAgY29sLnB1c2hfYmFjayhwb2ludHNbaV0pOwogICAgICAgICAgICB9CiAgICAgICAgfQoKICAgICAgICBwPSBxOwoKICAgICAgICBmb3IoaW50IGk9MDtpPGNvbC5zaXplKCk7aSsrKQogICAgICAgICAgICBodWxsLnB1c2hfYmFjayggY29sW2ldICk7CiAgICB9CiAgICB3aGlsZShwb2ludHNbcF0ueCE9cG9pbnRzW2xdLnggb3IgcG9pbnRzW3BdLnkhPXBvaW50c1tsXS55KTsKCgoKICAgIHNvcnQoIGh1bGwuYmVnaW4oKSwgaHVsbC5lbmQoKSwgY21wMSApOwogICAgYmFzZT0gaHVsbFswXTsKICAgIHNvcnQoIGh1bGwuYmVnaW4oKSsxLCBodWxsLmVuZCgpLCBjbXAyICk7CgogICAgaW50IHN6PSBodWxsLnNpemUoKTsKCiAgICBpbnQgY250PSAwOwogICAgZm9yKGludCBpPTA7IGk8c3o7IGkrKykKICAgIHsKICAgICAgICBpZihodWxsW2ldLng9PWJhc2UueCBhbmQgaHVsbFtpXS55PT1iYXNlLnkpCiAgICAgICAgICAgIGNvbnRpbnVlOwogICAgICAgIGNudCsrOwogICAgfQoKICAgIHdoaWxlKGh1bGwuc2l6ZSgpPDMpCiAgICAgICAgaHVsbC5wdXNoX2JhY2soYmFzZSk7CgoKICAgIGNvdXQ8PG1heChjbnQrMiwgMyk8PGVuZGw7CiAgICBjb3V0PDxiYXNlLng8PCIgIjw8YmFzZS55PDxlbmRsOwoKICAgIGludCBrPTA7CiAgICBzej0gaHVsbC5zaXplKCk7CgogICAgZm9yKGludCBpPTA7IGk8c3o7IGkrKykKICAgIHsKICAgICAgICAvL2NvdXQ8PGs8PGVuZGw7CiAgICAgICAgaWYoaHVsbFtpXS54PT1iYXNlLnggYW5kIGh1bGxbaV0ueT09YmFzZS55KQogICAgICAgIHsKICAgICAgICAgICAgaysrOwogICAgICAgICAgICBpZihrPD0yKQogICAgICAgICAgICAgICAgY29udGludWU7CiAgICAgICAgfQogICAgICAgIGNvdXQ8PGh1bGxbaV0ueDw8IiAiPDxodWxsW2ldLnk8PGVuZGw7CiAgICB9CiAgICBjb3V0PDxiYXNlLng8PCIgIjw8YmFzZS55PDxlbmRsOwp9CgppbnQgbWFpbigpCnsKICAgIGludCB0YzsKICAgIGNpbj4+dGM7CiAgICBjb3V0PDx0Yzw8ZW5kbDsKICAgIGZvcihpbnQgdD0xOyB0PD10YzsgdCsrKQogICAgewogICAgICAgIGludCBuOwogICAgICAgIGNpbj4+bjsKICAgICAgICBwb2ludCBwb2ludHNbbl07CgogICAgICAgIGZvcihpbnQgaT0wOyBpPG47IGkrKykKICAgICAgICB7CiAgICAgICAgICAgIHBvaW50IHA7CiAgICAgICAgICAgIGNpbj4+cC54Pj5wLnk7CiAgICAgICAgICAgIHBvaW50c1tpXT0gcDsKICAgICAgICB9CgogICAgICAgIGludCBsOwogICAgICAgIGlmKHQhPXRjKQogICAgICAgICAgICBjaW4+Pmw7CgogICAgICAgIGNIdWxsKHBvaW50cywgbik7CgogICAgICAgIGlmKHQhPXRjKQogICAgICAgICAgICBjb3V0PDxsPDxlbmRsOwogICAgfQp9Cg==
MwoxNQozMCAzMAo1MCA2MAo2MCAyMAo3MCA0NQo4NiAzOQoxMTIgNjAKMjAwIDExMwoyNTAgNTAKMzAwIDIwMAoxMzAgMjQwCjc2IDE1MAo0NyA3NgozNiA0MAozMyAzNQozMCAzMAotMQoxMgo1MCA2MAo2MCAyMAo3MCA0NQoxMDAgNzAKMTI1IDkwCjIwMCAxMTMKMjUwIDE0MAoxODAgMTcwCjEwNSAxNDAKNzkgMTQwCjYwIDg1CjUwIDYwCi0xCjYKNjAgMjAKMjUwIDE0MAoxODAgMTcwCjc5IDE0MAo1MCA2MAo2MCAyMAo=
3
15
30 30
50 60
60 20
70 45
86 39
112 60
200 113
250 50
300 200
130 240
76 150
47 76
36 40
33 35
30 30
-1
12
50 60
60 20
70 45
100 70
125 90
200 113
250 140
180 170
105 140
79 140
60 85
50 60
-1
6
60 20
250 140
180 170
79 140
50 60
60 20