HEADQRT - Farthest Headquarters

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| ≤ 108, 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

Được gửi lên bởi:Duc
Ngày:2009-01-04
Thời gian chạy:0.170s
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.