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
Input: stdin
Output: stdout
Problem source:
Ðề thi học sinh giỏi quốc gia 2013-2014
Problem types
Allowed languages
C, C++, Go, Java, Kotlin, Pascal, PyPy, Python, Rust, Scratch

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.


  • 0
    ijk  commented on April 5, 2026, 10:40 a.m.

    Sol tham khảo:

    Giải trường hợp 2 xanh 1 đỏ, tương tự với 2 đỏ 1 xanh

    Tạm gọi 2 điểm xanh đang xét lần lượt là x1 và x2

    Ba điểm thẳng hàng khi và chỉ khi vector chỉ phương của (x1, đỏ) cùng phương với vector chỉ phương của (x2, đỏ)

    Vì vậy chúng ta sẽ cố định đỏ và duyệt hết các điểm xanh. Xét điểm xanh thứ ~i~, nếu đã xuất hiện vector chỉ phương nào giống với vector chỉ phương của cặp (i, đỏ) trước đó thì đó là đáp án của bài toán. Có thể sử dụng map để lưu trữ các vector chỉ phương trước đó.

    Khi thực hiện tìm cả 2 trường hợp nhưng không tồn tại bộ ba thỏa mãn thì in ~-1~


  • -7
    neptune_170_nt  commented on Jan. 7, 2023, 10:07 a.m.

    This comment is hidden due to too much negative feedback. Show it anyway.


  • -6
    nghiabom9999  commented on Oct. 14, 2022, 7:51 a.m.

    This comment is hidden due to too much negative feedback. Show it anyway.


    • -13
      vanhjjsdj  commented on Oct. 14, 2022, 8:20 a.m. ← edited

      This comment is hidden due to too much negative feedback. Show it anyway.