Hình học cơ bản

View as PDF
Submit solution
Points: 350.00 (partial)
Time limit: 1.0s
Memory limit: 256M
Input: stdin
Output: stdout
Authors:
UltimateWiener, LeKienThanh
Problem source:
steveonalex's kitchen
Problem type
Allowed languages
C++ (Themis), Pascal, Python

Cho bàn bi băng có kích cỡ N∗M đơn vị, ta quy ước các hàng được đánh số từ trái sang phải, các cột được đánh số từ trên xuống dưới. Ô (x,y) là giao của hàng x và cột y.

Có Q truy vấn, mỗi truy vấn có dạng (x,y,α,k), tức là giả sử bạn đặt bi cái ở ô (x,y), căn một góc α và bắn bi với một lực sao cho bi cái sẽ di chuyển đúng 2×k đơn vị. Hỏi bi cái sẽ đập băng bao nhiêu lần (nếu ta giả sử rằng không có lực ma sát giữa mặt bàn và bi cái và bi cái sẽ lập tức dừng lại sau khi đi đúng k đơn vị). Nếu bi cái chạm vào góc và bật lại, ta coi như bi cái chỉ đập băng 1 lần.

Bởi vì đề ban đầu quá dễ, nên α sẽ được giới hạn bởi các góc chéo (góc 45∘,135∘,225∘,315∘).

Các góc ở đây được hiểu theo nghĩa là góc lượng giác. Bạn có thể xem kỹ hơn về bảng giá trị góc lượng giác trong hình dưới đây.

Trigo

Input

  • Dòng đầu tiên nhập hai số N, M (3≤N,M≤109) là số hàng và số cột của bàn bi.
  • Dòng thứ hai nhập vào một số Q (1≤Q≤105) là số truy vấn.
  • Q dòng sau, mỗi dòng nhập vào bốn số x,y,α,k (1≤x≤N,1≤y≤M,α∈{45,135,225,315},1≤k≤1018) lần lượt là vị trí xuất phát, góc bắn và quãng đường mà bi cái sẽ di chuyển.

Output

  • Gồm Q dòng, dòng thứ i thể hiện cho truy vấn thứ i.

Sample Input

Copy
3 4
2
2 2 315 4
2 3 315 4

Sample Output

Copy
3
2

Scoring

Subtask Điểm Giới hạn
1 25% N,M≤100,k≤104,Q≤103
2 25% N,M≤105,Q≤10
3 25% N,M≤105
4 25% Không ràng buộc gì thêm

Comments

Please read the guidelines before commenting.


  • 0
    NoobCpp  commented 3:15:44 pm, 08/11/2024

    Nhìn cái hình học ở đề bài là hết cơ bản rồi ad ơi =))