1 #include<iostream>  2 #include<cstring>  3 #include<cstdio>  4 #include<string>  5 #include<algorithm>  6 #include<queue>  7 #include<cmath>  8 #include<vector>  9  10 using namespace std; 11  12 #define mnx 50050 13 #define LL long long 14 #define mod 1000000007 15 #define inf 0x3f3f3f3f 16 #define eps 1e-8 17 #define Pi acos(-1.0); 18 #define lson l, m, rt << 1 19 #define rson m+1, r, rt << 1 | 1 20  21 int dcmp( double x ){ 22     if( fabs( x ) < eps ) return 0; 23     return x < 0 ? -1 : 1; 24 } 25 struct point{ 26     double x, y; 27     point( double x = 0, double y = 0 ) : x(x), y(y) {} 28     point operator + ( const point &b ) const{ 29         return point( x + b.x, y + b.y ); 30     } 31     point operator - ( const point &b ) const{ 32         return point( x - b.x, y - b.y ); 33     } 34     point operator * ( const double &k ) const{ 35         return point( x * k, y * k ); 36     } 37     point operator / ( const double &k ) const{ 38         return point( x / k, y / k ); 39     } 40     bool operator < ( const point &b ) const{ 41         return dcmp( x - b.x ) < 0 || dcmp( x - b.x ) == 0 && dcmp( y - b.y ) < 0; 42     } 43     bool operator == ( const point &b ) const{ 44         return dcmp( x - b.x ) == 0 && dcmp( y - b.y ) == 0; 45     } 46     double len(){ 47         return sqrt( x * x + y * y ); 48     } 49 }; 50 typedef point Vector; 51 struct line{ 52     point p;  53     Vector v; 54     double ang; 55     line() {} 56     line( point p, point v ) : p(p), v(v) { 57         ang = atan2( v.y, v.x ); 58     } 59     bool operator < ( const line &b ) const{ 60         return ang < b.ang; 61     } 62 }; 63 double dot( Vector a, Vector b ){ 64     return a.x * b.x + a.y * b.y; 65 } 66 double cross( Vector a, Vector b ){ 67     return a.x * b.y - a.y * b.x; 68 } 69 bool onleft( line l, point p ){ 70     return cross( l.v, p - l.p ) > 0; 71 } 72 point getintersection( line a, line b ){ 73     Vector u = a.p - b.p; 74     double t = cross( b.v, u ) / cross( a.v, b.v ); 75     return a.p + a.v * t; 76 } 77 point pp[mnx]; 78 line q[mnx]; 79 int halfplaneintersection( line *L, int n, point *poly ){ 80     //sort( L, L + n ); 81     int first, last; 82     q[first = last = 0] = L[0]; 83     for( int i = 1; i < n; i++ ){ 84         while( first < last && !onleft( L[i], pp[last-1] ) ) last--; 85         while( first < last && !onleft( L[i], pp[first] ) ) first++; 86         q[++last] = L[i]; 87         if( fabs( cross( q[last].v, q[last-1].v ) ) < eps ){ 88             last--; 89             if( onleft( q[last], L[i].p ) ) q[last] = L[i]; 90         } 91         if( first < last ) pp[last-1] = getintersection( q[last-1], q[last] ); 92     } 93     while( first < last && !onleft( q[first], pp[last-1] ) ) last--; 94     if( last - first <= 1 ) return 0; 95     pp[last] = getintersection( q[last], q[first] ); 96     int m = 0; 97     for( int i = first; i <= last; i++ ){ 98         poly[m++] = pp[i]; 99     }100     return m;101 }102 point p[mnx], poly[mnx];103 line l[mnx];104 bool check( int n, int m ){105     if( n - m <= 2 ) return 1;106     for( int i = 0; i < n; i++ ){107         l[i] = line( p[i], p[i] - p[(i+m+1)%n] );108     }109     int all = halfplaneintersection( l, n, poly );110     if( !all ) return 1;111     else return 0;112 }113 int main(){114     int n, cas;115     scanf( "%d", &cas );116     while( cas-- ){117         scanf( "%d", &n );118         for( int i = 0; i < n; i++ ){119             scanf( "%lf %lf", &p[i].x, &p[i].y );120         }121         if( n > 50000 ) continue;122         int l = 0, r = n, ans;123         while( l < r ){124             int m = ( l + r ) >> 1;125             if( check( n, m ) == 1 ){126                 ans = m, r = m;127             }128             else l = m + 1;129         }130         printf( "%d\n", ans );131     }132     return 0;133 }