trang chủ / đề bài / icpcwf12_h

Phục vụ phòng

Đề bài

Mô tả

Bạn đang làm việc cho một công ty thiết kế những chú robot hút bụi dễ thương và vui nhộn. Ở mức tổng quát, hành vi của robot được chia thành ba chế độ:

  • Khám phá
  • Hút bụi
  • Tàn sát không kiểm soát

Đáng tiếc là trong khi thử nghiệm với người tiêu dùng cho thấy hai chế độ sau hoạt động hoàn hảo, chế độ khám phá vẫn còn lỗi. Bạn được giao nhiệm vụ gỡ lỗi.

Khi bắt đầu chế độ khám phá, robot được đặt vào một căn phòng có dạng đa giác lồi. Robot có cảm biến cho biết vị trí của mọi bức tường. Công việc của bạn là viết chương trình kiểm tra các số đo này có đúng hay không. Để làm vậy, robot cần chạm vật lý vào mọi bức tường trong phòng.

Bài toán của bạn như sau: cho hình dạng của một căn phòng đa giác lồi có N bức tường (mỗi bức tường là một cạnh của đa giác) và một điểm xuất phát P nằm bên trong phòng, hãy tìm độ dài của lộ trình ngắn nhất xuất phát từ P, chạm vào mọi bức tường rồi quay trở về P. Chạm vào một góc phòng (một đỉnh của đa giác) được tính là chạm vào cả hai bức tường kề với góc đó.

Dữ liệu vào

Dữ liệu gồm nhiều bộ test, đọc tới hết file. Mỗi bộ test bắt đầu bằng một dòng chứa số đỉnh N của đa giác (3≤N≤100) và hai số nguyên Px, Py là tọa độ điểm xuất phát của robot (−10000≤Px,Py≤10000). Tiếp theo là N dòng, mỗi dòng chứa hai số nguyên x, y (−10000≤x,y≤10000) là tọa độ một đỉnh của đa giác.

Các đỉnh được cho theo thứ tự ngược chiều kim đồng hồ, mọi góc trong đều nhỏ hơn 180 độ, đa giác không tự cắt, và điểm xuất phát của robot nằm hẳn bên trong đa giác.

Dữ liệu ra

Với mỗi bộ test, in số thứ tự bộ test và độ dài của lộ trình cần tìm theo dạng Case i: L (bộ test đánh số từ 1). Độ dài cần chính xác tới hai chữ số sau dấu chấm thập phân (đáp án được chấp nhận nếu sai lệch không quá 0.01 so với đáp án của ban giám khảo).

Ràng buộc

  • 3≤N≤100.
  • −10000≤Px,Py,x,y≤10000, mọi tọa độ là số nguyên.
  • Đa giác lồi ngặt, đỉnh cho theo thứ tự ngược chiều kim đồng hồ; P nằm hẳn bên trong đa giác.

Ví dụ

Input Output Giải thích
4 0 0
-1 -1
1 -1
1 1
-1 1
3 10 1
0 0
30 0
0 20
Case 1: 5.66
Case 2: 36.73
Bộ 1: phòng hình vuông cạnh 2, robot ở tâm; lộ trình ngắn nhất là hình thoi nối trung điểm bốn cạnh, dài 42≈5.66. Bộ 2: phòng tam giác vuông, lộ trình ngắn nhất dài khoảng 36.7277.
3 1 1
40 0
0 30
0 0
Case 1: 48.00 Phòng tam giác vuông với các đỉnh (40,0), (0,30), (0,0), robot ở (1,1). Lộ trình ngắn nhất lần lượt chạm ba bức tường (mỗi lần chạm, góc tới bằng góc phản xạ), dài khoảng 48.0017, làm tròn thành 48.00.

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