VOI 14 Bài 4 - Trò Chơi Với Những Viên Bi

View as PDF

Submit solution

Points: 0.66 (partial)
Time limit: 1.0s
Memory limit: 512M

Problem source:
Ðề thi học sinh giỏi quốc gia 2013-2014
Problem type
Allowed languages
C, C++, Java, Pascal, Python, TEXT

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 nhau và sao cho trong số đó có ~2~ bi đỏ và ~1~ bi xanh (khi đó ăn được một bi đỏ), hoặc là có ~2~ bi xanh và ~1~ bi đỏ (khi đó được ăn một bi xanh).

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.

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ì.

Giới hạn

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

Sample Input

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

Sample Output

1 2 4

Comments

Please read the guidelines before commenting.


There are no comments at the moment.