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


Submit solution

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

Problem type

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

There are no comments at the moment.