trang chủ / đề bài / icpc20_reg_c

Đường cao tốc Cần Thơ

Đề bài

Mô tả

Chủ tịch thành phố Cần Thơ đang lên kế hoạch xây một đường cao tốc mới. Đường cao tốc sẽ nối Cần Thơ với Thành phố Hồ Chí Minh, mang lại thịnh vượng cho cả vùng.

Tất nhiên, đường cao tốc không được cắt qua điểm du lịch nổi tiếng của Cần Thơ là chợ nổi Cái Răng, vốn không thể di dời. Nhiệm vụ của bạn là kiểm tra xem đường cao tốc mới có cắt qua chợ nổi Cái Răng hay không.

Cụ thể hơn, đường cao tốc được biểu diễn bởi hai đường thẳng song song a·x+b·y=c1 và a·x+b·y=c2: phần mặt phẳng nằm giữa hai đường thẳng này là đường cao tốc. Chợ nổi Cái Răng được biểu diễn gần đúng bởi một đa giác lồi có không quá 6 đỉnh. Hãy kiểm tra xem đường cao tốc và chợ nổi có phần chung với diện tích dương hay không.

Dữ liệu vào

  • Dòng đầu tiên chứa số nguyên t: số bộ dữ liệu.
  • Mỗi bộ dữ liệu gồm hai dòng:
    • Dòng thứ nhất chứa bốn số nguyên a, b, c1, c2.
    • Dòng thứ hai chứa số nguyên k: số đỉnh của đa giác lồi biểu diễn chợ nổi, tiếp theo là 2·k số nguyên x1 y1 x2 y2…xk yk: tọa độ các đỉnh của đa giác. Các đỉnh được liệt kê theo chiều kim đồng hồ hoặc ngược chiều kim đồng hồ.

Dữ liệu ra

Với mỗi bộ dữ liệu, in ra một dòng chứa YES nếu đường cao tốc và chợ nổi có phần chung với diện tích dương, ngược lại in ra NO.

Ràng buộc

  • 1≤t≤10000.
  • −100≤a,b,c1,c2≤100, a2+b2>0, c1≠c2.
  • 3≤k≤6.
  • −104≤xi,yi≤104.
  • Trong mỗi đa giác, không có hai đỉnh trùng tọa độ và không có ba đỉnh liên tiếp thẳng hàng.

Ví dụ

Input Output Giải thích
2
0 1 0 1
6 2 2 1 3 1 4 2 5 3 4 3 3
0 1 0 1
6 2 -1 1 0 1 1 2 2 3 1 3 0
NO
YES
Đường cao tốc là dải 0≤y≤1. Ở bộ thứ nhất, mọi đỉnh của đa giác có y≥2 nên đa giác nằm hẳn phía trên dải. Ở bộ thứ hai, đa giác trải từ y=−1 đến y=2, phần nằm trong dải có diện tích dương.
2
1 0 0 2
3 2 0 4 0 3 5
1 1 -5 5
4 -10 -10 10 -10 10 10 -10 10
NO
YES
Ở bộ thứ nhất, dải là 0≤x≤2 và tam giác nằm trong 2≤x≤4: hai hình chỉ chạm nhau tại đỉnh (2,0), diện tích chung bằng 0. Ở bộ thứ hai, dải −5≤x+y≤5 đi qua giữa hình vuông.

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