DOANCAT Kiểm tra đoạn thẳng cắt nhau

Cho 4 điểm A, B, C, D. Hãy kiểm tra xem hai đoạn thẳng AB và CD có cắt nhau không?

Input: dòng đầu ghi số t là số test case. Mỗi test case dạng:

• Một dòng duy nhất ghi 8 số nguyên là tọa độ 4 điểm. Mỗi số nguyên có trị tuyệt đối không quá 1000.

Output: ứng với mỗi test case xuất kết quả:

• Một dòng duy nhất ghi 1 nếu AB và CD cắt nhau, ngược lại xuất 0. (Nếu một điểm của đoạn này nằm trên đoạn kia thì không tính là cắt)

Input	Output
3 1 1 -1 -1 -1 1 1 -1 1 1 -1 -1 1 0 2 0 1 1 -1 -1 1 0 0 0	1 0 0