接力赛
You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.
题目描述
你正在参加国际接力邮寄大赛(International Conductive Posting Contest, ICPC),现在你需要从你的接力点到目的地。
由于阳光过于刺眼,如果你背对阳光,亦或是垂直于光线行走,那么你将不会受到阳光的刺激。北回归线以北的阳光正午时分几乎总是从正南方照射而来,恰好你此时接到了差事需要从 点前往 点。
我们约定太阳总是从你的正南方照射,如果你尝试往介于东南,西南和南方等存在有向南分量的方向行走,你将会感觉到阳光很刺眼。幸运的是你所在的城市有不少建筑,你可以从楼内(或边缘)穿梭过去,无论你朝哪个方向行走都不会受到刺激。
现在请你计算你从 点前往 点必须在阳光下(即阳光刺眼的情况下)行走的最短距离。
输入描述
第一行输入包含五个整数 和 ,其中 是阴影区域的数量满足 , 是 点坐标,是 点坐标,满足 $-1\times 10^6 \leqslant x_a, y_a, x_b, y_b \leqslant 1\times 10^6$。
太阳从正南方向北照射,即单位向量 为从 到 。如果你的方向向量 满足 ,你将会受到太阳的刺激。也就是说如果你朝方向 行走,其中 且 为任意值,那么你就会直视太阳。
接下来的 行描述了楼宇区域,它们是与坐标轴对齐的矩形,你可以在这里随意穿梭,包括楼宇边界。每行包含四个整数 和 。矩形的西南角是 ,东北角是 。描述阴影区域的矩形之间可能相互接触或相交。它们满足$-1\times 10^6 \leqslant x_1 < x_2 \leqslant 1\times 10^6$;$-1\times 10^6 \leqslant y_1 < y_2 \leqslant 1\times 10^6$。
输出描述
有时候我们不得不面对刺眼的阳光行走,输出你必须在阳光下(即阳光刺眼)行走的最短距离。如果你给出的浮点数答案 与裁判答案 的精度满足 将会被视为正确答案。
样例
2 1 7 5 1
3 6 5 9
2 3 6 5
3.0
2 0 10 10 0
2 7 3 8
4 3 8 5
7.0
2 11 -1 -1 11
2 7 3 8
4 3 8 5
0.0
3 1 5 9 5
-5 6 2 9
4 7 12 8
1 1 7 3
0.0
注释

如图展示了第一组样例一条 点到 点的最优路径,包含 5 段直线路程。在第一段,你背对太阳行走。在第二段和第四段,你虽然面向太阳行走,但位于阴影区域内。在第三段和第五段,你在阴影区域外面向太阳行走,这两段的总长度是 3.0。
2026江南程序设计竞赛联盟暑期多校训练-第二场(重现)
- Status
- Done
- Rule
- XCPC
- Problem
- 13
- Start at
- 2026-11-2 22:30
- End at
- 2026-11-3 0:30
- Duration
- 2 hour(s)
- Host
- Partic.
- 0