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

Nguồn đề bài: http://vn.spoj.com/problems/BALLGMVN/

1. Đề bài BALLGMVN spoj

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

2. Hướng dẫn giải BALLGMVN spoj – VOI 2014

Với mỗi điểm[i] từ 1–>N:

  • Xem điểm[i] là gốc tọa độ, nên dựng được xNew[j]=x[j]-x[i] và yNew[j]=y[j]-y[i] với 1<=j<=N.
  • Sort các điểm theo giá trị x/y.
  • Các điểm có cùng giá trị chính là các điểm trên cùng một đường thẳng.

ĐPT: O(N^2 log N)

Với cách trên các bạn sẽ gặp chút rắc rối ở viên bi màu. vậy các bạn có thể chọn i làm gốc tọa độ của 1 tập, còn tập kia chỉ cần chọn 2 điểm có tỉ số x/y như hướng dẫn ở trên bằng nhau là được. Như vậy, các bạn có thể chia thành 2 tập viên bị màu xanh và viên bi màu đỏ. và làm tương tự như cách ở trên 2 lần.

3. Code tham khảo BALLGMVN spoj – VOI 2014

Trả lời

Email của bạn sẽ không được hiển thị công khai. Các trường bắt buộc được đánh dấu *