trang chủ / đề bài / icpc25_mb_g

Tia laser

Đề bài

Mô tả

Thanh đã chia mặt phẳng Oxy thành n+1 môi trường thẳng đứng khác nhau với chiết suất lần lượt là a0,a1,a2,…,an (không nhất thiết phân biệt). Môi trường đầu tiên là không khí bình thường (a0=1).

Các môi trường được ngăn cách bởi n đường biên thẳng đứng h1 đến hn (−∞=h0<h1<h2<⋯<hn<hn+1=+∞). Như vậy, môi trường thứ i là phần nằm giữa hai đường thẳng x=hi và x=hi+1.

Bây giờ Thanh chiếu q tia laser từ q điểm (xi,yi) nằm trong môi trường đầu tiên, hướng về điểm (zi,ti) (1≤i≤q). Thanh cần tìm tổng độ dài mà mỗi tia đã đi được tính từ điểm xuất phát cho đến khi nó chạm tới môi trường thứ n lần đầu tiên. Dữ liệu đảm bảo tia sáng cuối cùng sẽ chạm tới môi trường thứ n.

Mọi tia laser đều tuân theo định luật khúc xạ Snell. Nói ngắn gọn, n1sinθ1=n2sinθ2, trong đó θi là góc giữa tia sáng và pháp tuyến (trục x), còn n1,n2 là chiết suất của hai môi trường.

Dữ liệu vào

Dòng đầu tiên chứa hai số nguyên dương n và q (1≤n,q≤105).

Dòng thứ i trong n dòng tiếp theo chứa hai số nguyên hi và ai (0≤hi≤109, 1≤ai≤109).

Dòng thứ i trong q dòng cuối cùng chứa bốn số nguyên xi,yi,zi,ti (0≤xi<zi, xi<h1, −1000≤xi,yi,zi,ti≤1000).

Dữ liệu ra

Với mỗi truy vấn, in ra một số thực trên một dòng. Đáp án được coi là đúng nếu sai số tuyệt đối hoặc sai số tương đối không vượt quá 10−4.

Ràng buộc

  • 1≤n,q≤105.
  • 0≤h1<h2<⋯<hn≤109, 1≤ai≤109.
  • 0≤xi<zi≤1000, xi<h1, −1000≤yi,ti≤1000.

Ví dụ

Input Output Giải thích
3 1
3 6
6 3
9 9
1 1 2 2
8.936454547 Tia đi theo hướng (1,1): trong không khí đi từ x=1 đến x=3 (độ dài 22), sau đó qua môi trường 1 (chiết suất 6) và môi trường 2 (chiết suất 3), dừng ở x=h3=9.
1 2
5 7
0 0 1 0
1 2 4 -2
5.000000000
6.666666667
Ví dụ bổ sung (không có trong đề gốc). Với n=1, tia chỉ cần đi trong không khí tới x=h1=5. Tia thứ hai có hướng (3,−4) nên đi được 4·53.

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