Problem hidden
|This problem was hidden by Editorial Board member probably because it has incorrect language|version or invalid test data, or description of the problem is not clear.|

BALLGMVN - VOI 2014 - Trò Chơi Với Những Viên Bi

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/ballgmvn


Trong một hội thi Ballgame, ban tổ chức chuẩn bị một bàn lớn. Trên mặt bàn có n bi xanh đánh số từ 1 đến n và n bi đỏ đánh số từ n + 1 đến 2n. Mỗi trận đấu, các vận động viên sẽ chơi luân phiên nhau. Đến lượt chơi của mình, Hùng cần tìm 3 bi mà vị trí của chúng là thằng hàng hanu và sao cho trong số đó có hai bi đỏ và 1 bi xanh (khi đó ăn được một bi đỏ), hoặc là có hai bi xanh và 1 bi đỏ (khi đó được ăn 1 bi xanh).

Yêu cầu

Cho biết tọa độ trên mặt phẳng tọa độ Đề-các của vị trí và màu của các bi hiện tại trên bàn, bạn hãy giúp Hùng chọn 3 bi để chơi.

Input

  • Dòng đầu ghi số nguên dương n.
  • Dòng thứ i trong số n dòng tiếp theo ghi hai số nguyên là hoành độ và tung độ trên mặt phẳng tọa độ Đề-các của vị trí đặt bi xanh với chỉ sô i.
  • Dòng thứ i trong số n dòng cuối cùng ghi hai số nguyên là hoàng độ và tung độ trên mặt phẳng tọa độ Đề-các của vị trí đặt bi đỏ với chỉ số n + i.
  • Hoàng độ và tung độ không vượt quá 10^6, vị trí các bi là đôi một phân biệt.

Giới hạn

  • 30% số test có n <= 2;
  • 30% số test khác có n <= 100.
  • 40% số test còn lại có n <= 1000.

Output

Ghi ra 3 chỉ số của các viên bi mà Hùng cần chọn, nếu không thể chọn được 3 bi nào, ghi ra -1. Nếu có nhiều đáp án, ghi ra một đáp án bất kì.

Example

Input:
3
1 1
2 2
4 9
3 3
6 20
8 100

Output:
1 2 4

Được gửi lên bởi:VOJ Team
Ngày:2014-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ừ: ASM64 GOSU PERL6 PYPY RUST SED
Nguồn bài:Đề thi học sinh giỏi quốc gia 2013-2014

hide comments
2016-11-17 15:37:18
O(2n*(4n + (2n-1)log(2n-1) )) AC :3
2016-09-27 18:33:24 minhsn
trau k ac dau
2016-07-25 10:10:04 Lê Thanh Phú
Nhiều khi AC đến vu vơ với tích vector O(n*n*log(n))
2016-05-23 02:54:56 xin đừng quên tôi
THAM KHẢO THUẬT TOÁN VÀ CODE TẠI: http://yeulaptrinh.pw/175/ballgmvn-spoj/

Last edit: 2016-09-30 01:18:40
2016-05-14 11:39:17 Nghia
có thể chia, dùng thêm một hàm if làm trường hợp đặc biệt là được
2016-02-21 18:18:09 Nguyễn Thành Nhân
Bài hay, thuật toán vi diệu vc

Last edit: 2016-02-22 04:44:53
2016-01-07 10:52:24 Vu Duy Truc
Chu y: 1 testcase n=1
2016-01-05 04:56:40
trâu AC
2015-12-30 08:46:44
O(4*n^2 log(2*n)) mà sao có 90 đ :'(( ai AC rồi chí với !!!
2015-11-15 03:24:06
tham khảo nè mọi người: http://www.oni.vn/af8kJ
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.