Farthest Headquarters

View as PDF

Submit solution

Points: 0.75 (partial)
Time limit: 1.0s
Memory limit: 512M
Input: stdin
Output: stdout

Problem source:
ACM Regional, Ho Chi Minh City 2008
Problem types
Allowed languages
C, C++, Java, Kotlin, Pascal, PyPy, Python, Scratch

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.

Input

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 \leq n \leq 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 ~x_i, y_i, c_i~ (~0 \leq |x_i|, |y_i| \leq 10^{8}~, ~0 \leq c_i \leq 1~) cách nhau bởi dấu trống, với ~(x_i, y_i)~ là tọa độ của văn phòng thứ ~i~ và nó là văn phòng của Microhoo nếu ~c_i = 0~ và Googloo nếu ~c_i = 1~.

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

Output

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.

Sample Input

2
2
0 0 0
3 -2 1
5
1 5 1
-5 2 0
3 7 1
6 -2 0
5 1 0

Sample Output

3
9

Comments

Please read the guidelines before commenting.


There are no comments at the moment.