Trong lĩnh vực phát hiện đối tượng (Object Detection), người ta thường sử dụng chỉ số IOU (Intersection over Union) để đánh giá mức độ trùng khớp giữa hộp chứa chuẩn (ground truth bounding box) và hộp chứa dự đoán (predicted bounding box). Chỉ số này được định nghĩa như sau:

$$ IOU = \frac{\text{Diện tích phần giao nhau (Intersection)}}{\text{Diện tích phần hợp nhất (Union)}} $$

Nhiệm vụ

Bạn được cho nhiều testcase, mỗi testcase bao gồm:

• Tọa độ của hai hình chữ nhật (bounding box) trên mặt phẳng tọa độ:
• Hộp chứa chuẩn (Ground Truth): Gồm 4 cặp tọa độ tương ứng với 4 đỉnh của hình chữ nhật $$(x_1, y_1), (x_2, y_2), (x_3, y_3), (x_4, y_4)$$.
• Hộp chứa dự đoán (Predicted Box): Gồm 4 cặp tọa độ tương ứng với 4 đỉnh của hình chữ nhật $$(x'_1, y'_1), (x'_2, y'_2), (x'_3, y'_3), (x'_4, y'_4)$$.

Dữ liệu vào:

• Dòng đầu tiên là số lượng testcase T.
• Với các mỗi testcase, data đầu vào sẽ có dạng.
• $$(x_1, y_1), (x_2, y_2), (x_3, y_3), (x_4, y_4)$$
• $$(x'_1, y'_1), (x'_2, y'_2), (x'_3, y'_3), (x'_4, y'_4)$$
• Các hình chữ nhật đều được đảm bảo là song song với trục hoành hoặc trục tung của hệ tọa độ Oxy.

Dữ liệu ra:

• Gồm ~T~ dòng, mỗi dòng là chỉ số IOU tương ứng. Hãy làm tròn kết quả đến 5 chữ số sau phần thập phân.

Input:

2
0 0 0 2 2 2 2 0
1 1 1 3 3 3 3 1
0 0 0 3 3 3 3 0
3 3 3 6 6 6 6 3

Output:

0.14286
0.00000

Giới hạn:

• ~1 \le T \le 1000~.
• Các tọa độ là các số nguyên nằm trong khoảng ~[0, 10^6]~.