English

Vietnamese

Hiện tại, bài tập này đã có trên online judge chính thức của VNOI, bạn có thể truy cập ở đây: https://oj.vnoi.info/problem/headqrt

Đọc đề đẹp hơn ở: 
https://codeforces.com/group/FLVn1Sc504/contest/274493/problem/I 

Microhoo và Googloo là hai công ty Tin học cạnh tranh nhau ở cùng một thành phố. Mỗi công ty có một số văn phòng nằm ở một số điểm trong thành phố. Để bảo vệ thông tin quan trọng khỏi lọt đến đối thủ, cả hai công ty đã cam kết sẽ đặt trụ sở chính càng xa nhau càng tốt.

Cho trước vị trí của các văn phòng của Microhoo và Googloo, nhiệm vụ của bạn là viết một chương trình để giúp hai công ty chọn từ các văn phòng đã có để đặt trụ sở chính sao cho khoảng cách giữa hai trụ sở chính của hai công ty là lớn nhất.

Dữ liệu vào

Dữ liệu vào gồm nhiều bộ dữ liệu tương ứng với nhiều test. Dòng đầu tiên chứa một số nguyên dương không lớn hơn 20 là số lượng các bộ dữ liệu. Các dòng tiếp theo chứa các bộ dữ liệu.

Với mỗi bộ dữ liệu, dòng đầu tiên chứa số nguyên n (2 ≤ n ≤ 30000) là tổng số lượng văn phòng của cả hai công ty. Dòng thứ i trong n dòng tiếp theo chứa ba số nguyên xi, yi, ci (0 ≤ |xi|, |yi| ≤ 10⁸, 0 ≤ ci ≤ 1) cách nhau bởi dấu trống, với (xi, yi) là tọa độ của văn phòng thứ ith và nó là văn phòng của Microhoo nếu ci = 0 và Googloo nếu ci = 1.

Cho biết mỗi công ty có ít nhất một văn phòng.

Dữ liệu ra

Với mỗi bộ dữ liệu, ghi ra trên một dòng phần nguyên của khoảng cách lớn nhất giữa trụ sở chính của Microhoo và Googloo.

Ví dụ

Dữ liệu vào
2
2
0 0 0
3 -2 1
5
1 5 1 
-5 2 0
3 7 1
6 -2 0 
5 1 0

Dữ liệu ra
3
9