trang chủ / đề bài / icpcwf25_l

Bước đi dưới nắng

Đề bài

Mô tả

"I'm walking on sunshine, and it don't feel good, my eyes hurt!"

Baku có rất nhiều nắng. Nếu bạn đi theo hướng ngược với mặt trời, hoặc ít nhất là vuông góc với các tia nắng, thì nắng không chiếu vào mắt bạn. Trong bài này, giả sử mặt trời chiếu từ phía nam. Đi về hướng tây, hướng đông, hoặc bất kỳ hướng nào nằm giữa tây và đông có thành phần hướng bắc thì tránh được việc nhìn vào mặt trời. Mắt bạn sẽ bị chói nếu bạn đi theo bất kỳ hướng nào có thành phần hướng nam.

Baku cũng có nhiều vùng bóng râm hình chữ nhật, và khi ở trong các vùng này thì mắt bạn được bảo vệ dù bạn đi theo hướng nào.

Hãy tìm quãng đường nhỏ nhất bạn phải đi trong khi nắng chiếu vào mắt để đi từ địa điểm thi đấu tới địa điểm lễ trao giải.

Dữ liệu vào

Dòng đầu tiên chứa năm số nguyên n, xc, yc, xa và ya, trong đó n (0≤n≤105) là số vùng bóng râm, (xc,yc) là vị trí địa điểm thi đấu, và (xa,ya) là vị trí địa điểm lễ trao giải (−106≤xc,yc,xa,ya≤106). Mặt trời chiếu theo hướng (0,1), từ nam lên bắc. Bạn nhìn vào mặt trời nếu đi theo hướng (x,y) với y<0 bất kỳ và x bất kỳ.

Mỗi dòng trong n dòng tiếp theo mô tả một vùng bóng râm, là một hình chữ nhật có các cạnh song song với các trục tọa độ. Mỗi dòng chứa bốn số nguyên x1, y1, x2 và y2 (−106≤x1<x2≤106; −106≤y1<y2≤106). Góc tây nam của hình chữ nhật là (x1,y1) và góc đông bắc là (x2,y2). Các hình chữ nhật mô tả vùng bóng râm không chạm nhau và không giao nhau.

Dữ liệu ra

In ra quãng đường nhỏ nhất bạn phải đi trong khi nắng chiếu vào mắt. Đáp án của bạn được chấp nhận nếu sai số tuyệt đối hoặc sai số tương đối không quá 10−7.

Ràng buộc

  • 0≤n≤105.
  • −106≤xc,yc,xa,ya≤106.
  • −106≤x1<x2≤106, −106≤y1<y2≤106.
  • Các hình chữ nhật không chạm nhau và không giao nhau.

Ví dụ

Input Output Giải thích
2 1 7 5 1
3 6 5 9
2 3 6 5
3.0 Một đường đi tối ưu gồm 5 đoạn: (1,7)→(3,8)→(4,6)→(4,5)→(5,3)→(5,1). Đoạn thứ nhất đi ra xa mặt trời (về phía bắc). Đoạn thứ hai và thứ tư đi về phía mặt trời nhưng nằm trong vùng bóng râm. Đoạn thứ ba và thứ năm đi về phía mặt trời ngoài vùng bóng râm, tổng độ dài hai đoạn này là 1+2=3.
2 0 10 10 0
2 7 3 8
4 3 8 5
7.0 Chỉ các đoạn độ cao [7,8] và [3,5] có bóng râm che, phần còn lại của 10 đơn vị đi xuống phía nam phải đi dưới nắng: 10−1−2=7.
2 11 -1 -1 11
2 7 3 8
4 3 8 5
0.0 Lễ trao giải ở phía bắc địa điểm thi đấu, không bao giờ cần đi về phía nam.
3 1 5 9 5
-5 6 2 9
4 7 12 8
1 1 7 3
0.0 Hai địa điểm cùng độ cao: đi thẳng về hướng đông.
3 1 7 9 3
2 6 3 8
4 4 5 6
6 2 7 4
0.0 Các độ cao [6,8], [4,6], [2,4] đều có bóng râm, nên có thể đi xuống từ độ cao 7 tới độ cao 3 hoàn toàn trong bóng râm.
1 0 0 0 0
-5 -5 5 5
0.0 Hai địa điểm trùng nhau.

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