trang chủ / đề bài / icpc21_mt_i

Treo giấy khen

Đề bài

Mô tả

Qua nhiều năm tham dự Olympic Tin học Sinh viên Việt Nam và ICPC, Câu lạc bộ Olympic Tin học của Trường Đại học Bách khoa, Đại học Đà Nẵng đã nhận được rất nhiều giấy khen. Đội trưởng Khải của câu lạc bộ nảy ra ý tưởng làm một khu trưng bày các giấy khen này. Khải chuẩn bị n khung hình chữ nhật để treo chúng. Khung thứ i có kích thước (wi,hi) (rộng wi, cao hi, các cạnh song song với trục tọa độ) và được treo lên tường bằng một chiếc đinh đóng vào tâm khung, tại tọa độ (xi,yi) trên tường.

Tuy nhiên, sau khi treo xong, Khải nhận thấy một số khung bị chồng lên nhau. Khải quyết định điều chỉnh bằng cách chọn một số khung và xoay chúng 90 độ quanh tâm (khung xoay có kích thước (hi,wi)) sao cho không còn hai khung nào chồng lên nhau. Hai khung được coi là chồng lên nhau khi phần giao của chúng có diện tích dương; hai khung chỉ chạm nhau theo cạnh hoặc đỉnh thì không chồng lên nhau. Vì công việc khá khó, hãy giúp Khải.

Dữ liệu vào

  • Dòng đầu tiên chứa số nguyên dương n (1≤n≤2500).
  • n dòng tiếp theo, mỗi dòng chứa 4 số nguyên xi,yi,wi,hi (−109≤xi,yi≤109, 1≤wi,hi≤109).

Dữ liệu ra

  • Nếu không có cách xoay nào thỏa mãn, in ra No.
  • Ngược lại, dòng đầu tiên in ra Yes, dòng thứ hai in ra cách xoay dưới dạng một xâu gồm các ký tự Q hoặc K. Ký tự thứ i cho biết khung thứ i có được xoay hay không: Q nghĩa là xoay, K nghĩa là không xoay. Nếu có nhiều cách, in ra cách có thứ tự từ điển nhỏ nhất.

Ràng buộc

  • 1≤n≤2500.
  • −109≤xi,yi≤109, 1≤wi,hi≤109.

Ví dụ

Input Output Giải thích
4
0 2 2 4
0 0 2 4
4 0 4 2
4 2 2 4
Yes
QQKQ
Sau khi xoay, khung 1 chiếm [−2,2]×[1,3], khung 2 chiếm [−2,2]×[−1,1], khung 3 chiếm [2,6]×[−1,1], khung 4 chiếm [2,6]×[1,3]. Các khung chỉ chạm nhau theo cạnh.
2
0 0 2 2
1 1 2 2
No Hai khung vuông luôn chồng lên nhau dù xoay thế nào.

Bình luận

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

gnatmake 12.2.0 a68g 3.1.2 nasm 2.16.1 as_x64 2.47 awk 1.3.4 gcc 16.2.0 dotnet 10.0.402 g++ 16.2.0 g++-themis 16.2.0 g++17 16.2.0 g++20 16.2.0 g++23 16.2.0 clang++ 22.1.8 dmd 2.113.0 dart 3.13.6 gforth 0.7.3 gfortran 15.3.0 go 1.27.3 groovyc 5.1.3 javac 26.0.2.1 node 26.12.1 julia 1.13.2 kotlinc 2.4.21 lean 4.35.0 sbcl 2.2.9 lua 5.5.1 nim 2.2.12 fpc 3.2.2 fpc-themis 3.2.2 perl 5.42.3 php 8.5.12 pike 8.0 swipl 9.0.4 pypy3 7.3.23 python3 3.15.1 racket 8.7 ruby 4.0.8 rustc 1.99.1 csc 5.3.0 ctoj-scratch 0.0.1 sed 4.9 swiftc 6.4.1 tclsh 8.6 bun 1.4.4 deno 2.9.8 v 0.5.2 zig 0.17.0