HEADQRT - Farthest Headquarters

no tags 

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.


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.


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


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

Sample Output

Added by:Duc
Time limit:0.170s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ERL JS-RHINO NODEJS PERL6 VB.NET
Resource:ACM Regional, Ho Chi Minh City 2008