trang chủ / đề bài / icpcwf07_c

Đườ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 N đoạn thẳng nối tiếp nhau, tức là điểm cuối của đoạn thứ k trùng với điểm đầu của đoạn thứ k+1. 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 6 đ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 y. Mỗi tọa độ hai chiều (xi,yi) ứng với một điểm ba chiều (xi′,yi′,zi′), trong đó zi′ là độ cao của điểm cuối đoạn thứ i. Độ cao của gốc tọa độ bằng 0.

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 k là zk′ thì độ cao điểm cuối của mọi đoạn sau đoạn k không được nhỏ hơn zk′. Viết một cách hình thức: zk′≤zm′ với mọi m≥k.

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 N và θ: N 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 N dòng tiếp theo chứa một cặp số nguyên xi, yi (1≤i≤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 k+1 bắt đầu tại điểm cuối của đoạn k. Không có đoạn nào có độ dài bằng 0.

Sau bộ test cuối cùng là một dòng chứa hai số 0.

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ừ 1) theo sau là:

  • Acceptable as proposed nếu đường đua chấp nhận được mà không cần quay;
  • Acceptable after clockwise rotation of X degrees hoặc Acceptable after counterclockwise rotation of X degrees nế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ị X 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 y về phía tia dương của trục x. 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;
  • Unacceptable nế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

  • 1≤N≤104, 0≤θ≤45.
  • |xi|,|yi|≤106.
  • Tổng N trong một file không vượt quá 5·105.
  • 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à 5000…) hơn 10−6 độ, và hai góc quay theo hai chiều hoặc bằng nhau đúng, hoặc chênh nhau hơn 10−6 độ.

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 (−10,−9), xuống dốc. Bộ 3: các đoạn đi theo các hướng (10,10), (−9,0) và (4,−4), 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 y đi ngang (không lên không xuống), được phép. Bộ 3: θ=0 nên sườn đồi nằm ngang và không có đoạn nào xuống dốc. Bộ 4: quay 90 độ theo chiều nào cũng được, in counterclockwise cũng được chấp nhận.

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