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

Chúng tôi nhận thiết kế web công ty, thiết kế web thương mại điện tử, shop, thiết kế web blog cá nhân, viết phần mềm PC.

Liên hệ ngay: 035.870.8844 - Giá chỉ từ 2-3 triệu.

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 *