Đường đua trên sườn đồi
Đề bài
Mô tả
Bạn là kiến trúc sư trưởng của một cuộc đua ô tô sẽ được tổ chức ở vùng đồi núi. Đường đua gồm đoạn thẳng nối tiếp nhau, tức là điểm cuối của đoạn thứ trùng với điểm đầu của đoạn thứ . Trong lúc lên kế hoạch, các đoạn này được vẽ trên một mặt phẳng, nên các đầu mút được cho bằng tọa độ Descartes hai chiều. Đoạn thứ nhất bắt đầu tại gốc tọa độ. Hình 1 là hình chiếu bằng của một đường đua gồm đoạn.

Hình 1
Cuộc đua thật diễn ra trên sườn đồi. Để đơn giản, coi sườn đồi là một mặt phẳng tạo với mặt phẳng nằm ngang một góc , như trong Hình 2.

Hình 2
Mặt phẳng sườn đồi và mặt phẳng nằm ngang cắt nhau theo trục . Mỗi tọa độ hai chiều ứng với một điểm ba chiều , trong đó là độ cao của điểm cuối đoạn thứ . Độ cao của gốc tọa độ bằng .
Cuộc đua này dành cho người mới lái, nên đường đua không được có đoạn nào phải đi xuống dốc. Nghĩa là nếu độ cao của điểm cuối đoạn là thì độ cao điểm cuối của mọi đoạn sau đoạn không được nhỏ hơn . Viết một cách hình thức: với mọi .
Nếu đường đua đề xuất có đoạn xuống dốc, có thể biến nó thành đường đua không có đoạn xuống dốc bằng cách quay toàn bộ hình chiếu bằng của đường đua quanh gốc tọa độ (góc giữa các cặp đoạn liên tiếp không đổi). Tuy nhiên có những đường đua không thể trở nên chấp nhận được bằng bất kỳ phép quay nào.
Hãy xác định đường đua đề xuất có chấp nhận được không (tức là không có đoạn nào xuống dốc). Nếu không, hãy tìm góc nhỏ nhất cần quay đường đua để nó chấp nhận được, nếu điều đó có thể.
Dữ liệu vào
Dữ liệu vào gồm nhiều bộ test. Mỗi bộ test mô tả một đường đua đề xuất và độ dốc của sườn đồi nơi tổ chức đua. Dòng đầu tiên của mỗi bộ test chứa hai số nguyên và : là số đoạn của đường đua, là góc (tính bằng độ) giữa sườn đồi và mặt phẳng nằm ngang. Mỗi dòng trong dòng tiếp theo chứa một cặp số nguyên , () là điểm cuối của các đoạn thẳng tạo nên đường đua. Đoạn thứ nhất bắt đầu tại gốc tọa độ, và đoạn bắt đầu tại điểm cuối của đoạn . Không có đoạn nào có độ dài bằng .
Sau bộ test cuối cùng là một dòng chứa hai số .
Dữ liệu ra
Với mỗi bộ test, in một dòng gồm số thứ tự của bộ test (bắt đầu từ ) theo sau là:
Acceptable as proposednếu đường đua chấp nhận được mà không cần quay;Acceptable after clockwise rotation of X degreeshoặcAcceptable after counterclockwise rotation of X degreesnếu đường đua không chấp nhận được như đề xuất nhưng có thể trở nên chấp nhận được sau khi quay quanh gốc tọa độ. Giá trị là số không dấu. Phép quay theo chiều kim đồng hồ (clockwise) là phép quay đưa tia dương của trục về phía tia dương của trục . Nếu cả phép quay theo chiều kim đồng hồ lẫn ngược chiều kim đồng hồ (counterclockwise) đều làm đường đua chấp nhận được, hãy chọn phép quay có góc nhỏ hơn. Nếu hai góc bằng nhau thì in phép quay nào cũng được chấp nhận;Unacceptablenếu không có phép quay nào làm đường đua chấp nhận được.
Góc quay được làm tròn tới hai chữ số sau dấu thập phân.
In một dòng trống sau kết quả của mỗi bộ test. Làm theo đúng định dạng trong ví dụ.
Ràng buộc
- , .
- .
- Tổng trong một file không vượt quá .
- Dữ liệu đảm bảo góc quay cần in cách mốc làm tròn (giá trị có chữ số thập phân thứ ba trở đi là ) hơn độ, và hai góc quay theo hai chiều hoặc bằng nhau đúng, hoặc chênh nhau hơn độ.
Ví dụ
| Input | Output | Giải thích |
|---|---|---|
| 2 45 10 10 0 1 2 0 1 1 2 0 3 45 10 10 1 10 5 6 0 0 |
Case 1: Acceptable after clockwise rotation of 131.99 degrees Case 2: Acceptable as proposed Case 3: Unacceptable |
Bộ 1: đoạn thứ hai đi theo hướng , xuống dốc. Bộ 3: các đoạn đi theo các hướng , và , không có phép quay nào làm cả ba không xuống dốc. |
| 2 30 -3 -4 -6 -8 3 20 0 -5 10 0 10 5 2 0 -4 0 4 0 1 45 -7 0 0 0 |
Case 1: Acceptable after counterclockwise rotation of 36.87 degrees Case 2: Acceptable as proposed Case 3: Acceptable as proposed Case 4: Acceptable after clockwise rotation of 90.00 degrees |
Bộ 2: hai đoạn dọc theo trục đi ngang (không lên không xuống), được phép. Bộ 3: nên sườn đồi nằm ngang và không có đoạn nào xuống dốc. Bộ 4: quay độ theo chiều nào cũng được, in counterclockwise cũng được chấp nhận. |
Bình luận