Tính hệ số

Xem dạng PDF

Gửi bài giải

Điểm: 1,95 (OI)
Giới hạn thời gian: 1.0s
Giới hạn bộ nhớ: 256M
Input: stdin
Output: stdout

Nguồn bài:
Vũ Phúc Hoàng
Dạng bài
Ngôn ngữ cho phép
C, C++, Go, Java, Kotlin, Pascal, PyPy, Python, Rust, Scratch

Để chọn ra đội tuyển tham dự Olympic Tin học quốc tế (IOI), ~N~ thí sinh phải trải qua hai kỳ thi là thi học sinh giỏi quốc gia vòng ~2~ và Olympic Tin học châu Á Thái Bình Dương (APIO). Cả hai kỳ thi trên đều đã kết thúc, mỗi thí sinh đã biết kết quả của mình, trong đó với thí sinh thứ ~i~, ~X_i~ là kết quả thi vòng ~2~ còn ~Y_i~ là kết quả thi APIO của thí sinh đó. Tuy nhiên, dù đã biết kết quả nhưng các thí sinh vẫn chưa thể biết chắc liệu mình có được chọn vào đội tuyển IOI hay không, bởi vì người ta xếp hạng thí sinh theo tổng số điểm của hai cuộc thi nhân với hai hệ số nào đó. Tức là, ban tổ chức sẽ chọn ra hệ số là một cặp số thực dương ~(a~, ~b)~, sau đó điểm để xếp hạng IOI sẽ được tính bằng công thức: ~a \times X_i + b \times Y_i~. ~4~ thí sinh có điểm xếp hạng cao nhất sẽ được chọn vào đội tuyển IOI.

Mỗi thí sinh đều đã biết điểm của mình và điểm của những người khác, tuy nhiên họ rất hoang mang vì không biết hệ số được chọn có lợi cho mình hay không. Mỗi người đều muốn biết là, mình sẽ đứng cao nhất là thứ mấy và thấp nhất là thứ mấy, với tất cả các bộ hệ số có thể. Thứ hạng của một người được tính bằng số người có điểm xếp hạng cao hơn họ cộng thêm ~1~, lưu ý là với một cặp hệ số mà có nhiều người bằng điểm nhau thì một người không đứng trên những người bằng điểm họ. Cặp hệ số được chọn cũng phải là số dương. Hãy viết chương trình giúp họ trả lời câu hỏi đó.

Input

  • Dòng đầu gồm một số nguyên ~N~, số thí sinh tham gia thi.
  • ~N~ dòng tiếp theo, mỗi dòng gồm hai số nguyên ~X_i~ và ~Y_i~, kết quả thi của các thí sinh.

Output

  • In ra ~N~ dòng, mỗi dòng gồm hai số nguyên in cách nhau bởi dấu cách, lần lượt là thứ hạng cao nhất có thể và thứ hạng thấp nhất có thể của các thí sinh.

Giới hạn

  • ~1 \leq N \leq 2000~.
  • ~0 \leq X_i~, ~Y_i \leq 10^{6}~.
  • ~30\%~ số điểm có ~1 \leq N \leq 20~.
  • ~30\%~ số điểm khác có ~1 \leq N \leq 100~.

Sample Input

5
1 3
5 2
1 4
2 5
3 3

Sample Output

4 5
1 5
2 4
1 3
2 3

Bình luận

Hãy đọc nội quy trước khi bình luận.


Không có bình luận tại thời điểm này.