HEADQRT - Farthest Headquarters

Microhoo and Googloo are two competing IT companies from the same city. Each company has offices scattered across the city. To protect their critical information from each other, both companies have agreed to locate their headquarters as far from each other as possible.

Given the locations of Microhoo and Googloo existing offices, your task is to write a program to help the two companies to select their headquarters from existing offices so that the distance between their headquarters is longest.

Input

The input file consists of several data sets. The first line of the input file contains the number of data sets which is a positive integer and is not bigger than 20. The following lines describe the data sets.

For each data set, the first line contains the integer n (2 ≤ n ≤ 30000) representing the total number of offices for both companies. The ith line of the next n line contains three integers xi, yi, ci (0 ≤ |xi|, |yi| ≤ 108, 0 ≤ ci ≤ 1) separated by space, where (xi, yi) is the coordinate of the ith office and it is Microhoo’s office if ci = 0 and Googloo’s if ci = 1.

It is guaranteed that each company has at least one office.

Output

For each data test, write in one line the integer part of the longest distance between Microhoo’s and Googloo’s headquarters.

Example

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


Được gửi lên bởi:Jimmy
Ngày:2009-01-04
Thời gian chạy:1s
Giới hạn mã nguồn:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Ngôn ngữ cho phép:Tất cả ngoại trừ: ERL GOSU JS-RHINO NODEJS PERL6 PYPY RUST SED VB.NET
Nguồn bài:ACM Regional, Ho Chi Minh City 2008

hide comments
2017-07-06 12:47:03
bài này làm thế nào cho không quá thời gian vậy.Mình thì O(n^2) thôi :(((
2017-04-21 17:57:49
mất mấy lần sub vì lỗi ngáo -_-
@phanduy16
2013-09-10 14:34:56 X-71
Mình bị lỗi NZEC, sợt thì thấy hình như do đọc ghi sai. Mấy bạn đọc ghi sao v? >.<
2011-02-14 03:33:24 ðẹp trai bẩm sinh
Mình dùng C++, lúc đầu dùng sqrt sai kết quả, sau đó mình viết hàm căn bậc 2 trả về số 64bit thì AC :D
2010-11-08 16:22:44 BB
anh Đức ơi hình như bài này test cho x,y là số thực thì phải=.="
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.