1 //UVALive7461 - Separating Pebbles 判断两个凸包相交 2 3 #include <bits/stdc++.h> 4 using namespace std; 5 #define LL long long 6 typedef pair<int,int> pii; 7 const int inf = 0x3f3f3f3f; 8 const int N =1e5+10; 9 #define clc(a,b) memset(a,b,sizeof(a)) 10 const double eps = 1e-8; 11 const int MOD = 1e9+7; 12 void fre() {freopen("in.txt","r",stdin);} 13 void freout() {freopen("out.txt","w",stdout);} 14 inline int read() {int x=0,f=1;char ch=getchar();while(ch>'9'||ch<'0') {if(ch=='-') f=-1;ch=getchar();}while(ch>='0'&&ch<='9') {x=x*10+ch-'0';ch=getchar();}return x*f;} 15 16 int sgn(double x) { 17 if(fabs(x) < eps)return 0; 18 if(x < 0)return -1; 19 else return 1; 20 } 21 22 struct Point { 23 int x,y; 24 Point() {} 25 Point(int _x,int _y) { 26 x = _x; 27 y = _y; 28 } 29 Point operator -(const Point &b)const { 30 return Point(x - b.x,y - b.y); 31 } 32 int operator ^(const Point &b)const { 33 return x*b.y - y*b.x; 34 } 35 int operator *(const Point &b)const { 36 return x*b.x + y*b.y; 37 } 38 friend int dis2(Point a) { 39 return a.x*a.x+a.y*a.y; 40 } 41 friend bool operator<(const Point &a,const Point &b){ 42 if(fabs(a.y-b.y)<eps) return a.x<b.x; 43 return a.y<b.y; 44 } 45 }; 46 typedef Point Vector; 47 double Dot(Point A, Point B){return A.x*B.x+A.y*B.y;}//点积 48 double Cross(Vector A,Vector B){return A.x*B.y-A.y*B.x;}//叉积 49 double Length(Vector A){return sqrt(Dot(A,A));}//OA长 50 double Angle(Point A,Point B){return acos(Dot(A,B)/Length(A)/Length(B));}//OA和OB的夹角 51 //判断线段相交,不在端点相交 52 bool SegmentProperIntersection(Point a1,Point a2,Point b1,Point b2){ 53 double c1=Cross(a2-a1,b1-a1),c2=Cross(a2-a1,b2-a1),c3=Cross(b2-b1,a1-b1),c4=Cross(b2-b1,a2-b1); 54 return sgn(c1)*sgn(c2)<0&&sgn(c3)*sgn(c4)<0; 55 } 56 57 int graham(Point p[],int n,Point q[]){ 58 int top=1; 59 sort(p,p+n); 60 if(n==0) return 0; 61 q[0]=p[0]; 62 if(n==1) return 1; 63 q[1]=p[1]; 64 if(n==2) return 2; 65 q[2]=p[2]; 66 for(int i=2;i<n;i++){ 67 while(top&&(Cross(q[top]-q[top-1],p[i]-q[top-1])<=0)) top--; 68 q[++top]=p[i]; 69 } 70 int len=top; 71 q[++top]=p[n-2]; 72 for(int i=n-3;i>=0;i--){ 73 while(top!=len&&(Cross(q[top]-q[top-1],p[i]-q[top-1])<=0)) top--; 74 q[++top]=p[i]; 75 } 76 return top; 77 } 78 79 bool C_S(Point *ch1,int t1,Point *ch2,int t2)//判断凸包是否相交 80 { 81 double angle[1010],x; 82 int i,j,k,m; 83 if(t1==1)return true; 84 if(t1==2) 85 { 86 for(i=0;i<t2;i++) 87 { 88 k=sgn(Cross(ch1[1]-ch1[0],ch2[i]-ch1[0])); 89 if(k==0&&Dot(ch1[1]-ch1[0],ch2[i]-ch1[0])>0) 90 { 91 if(Length(ch2[i]-ch1[0])<Length(ch1[1]-ch1[0]))break; 92 } 93 } 94 if(i<t2)return false; 95 if(t2==2&&SegmentProperIntersection(ch1[0],ch1[1],ch2[0],ch2[1]))return false; 96 return true; 97 } 98 angle[0]=0; 99 for(i=2;i<t1;i++) 100 angle[i-1]=Angle(ch1[1]-ch1[0],ch1[i]-ch1[0]); 101 for(i=0;i<t2;i++) 102 { 103 j=sgn(Cross(ch1[1]-ch1[0],ch2[i]-ch1[0])); 104 if(j<0||(j==0&&Dot(ch1[1]-ch1[0],ch2[i]-ch1[0])<0))continue; 105 j=sgn(Cross(ch1[t1-1]-ch1[0],ch2[i]-ch1[0])); 106 if(j>0||(j==0&&Dot(ch1[t1-1]-ch1[0],ch2[i]-ch1[0])<0))continue; 107 x=Angle(ch1[1]-ch1[0],ch2[i]-ch1[0]); 108 m=lower_bound(angle,angle+t1-1,x)-angle; 109 if(m==0)j=0; 110 else j=m-1; 111 k=sgn(Cross(ch1[j+1]-ch2[i],ch1[j+2]-ch2[i])); 112 if(k>=0)break; 113 } 114 if(i<t2)return false; 115 return true; 116 } 117 118 Point p1[300],p2[300],ch1[300],ch2[300]; 119 int main(){ 120 int T; 121 scanf("%d",&T); 122 while(T--){ 123 int n; 124 scanf("%d",&n); 125 int cnt1=0,cnt2=0; 126 for(int i=0;i<n;i++){ 127 int x,y,c; 128 scanf("%d%d%d",&x,&y,&c); 129 if(c==0){ 130 p1[cnt1++]=Point(x,y); 131 } 132 else p2[cnt2++]=Point(x,y); 133 } 134 int t1=graham(p1,cnt1,ch1); 135 int t2=graham(p2,cnt2,ch2); 136 if(C_S(ch1,t1,ch2,t2)&&C_S(ch2,t2,ch1,t1)) printf("1 "); 137 else printf("0 "); 138 } 139 }