P4605 [SDOI2018]物理实验

    • 91通过
    • 272提交
  • 题目提供者 qqvq
  • 评测方式 云端评测
  • 标签 前缀和 向量 平衡树 各省省选 2018 山东 O2优化 Special Judge 高性能
  • 难度 NOI/NOI+/CTSC
  • 时空限制 10000ms / 512MB

题解

  • 提示:收藏到任务计划后,可在首页查看。
  • 体验新版界面

    最新讨论 显示

    推荐的相关题目 显示

    题目描述

    小 T 这学期有物理实验课,为了顺利完成下一节课的实验,他打算在课前对实验内容进行预习。

    这次实验在一个二维平面上进行,平面上放置了一条无限长的直线导轨,导轨上放置了一个长为$L$的激光发射器,激光发射器会向导轨两侧沿导轨垂直方向发射宽度为$L$的激光束。

    平面上还放置了 $n$ 个挡板,每个挡板可以看作是一条线段,现在每个挡板都不和直线导轨接触,且 和直线导轨的夹角不超过 $85 \degree$,任意两个挡板也不会相互接触,激光束不能穿透这些挡板,并且会被挡板吸收掉,不会被挡板反射出去。

    小 T 想确定一个激光发射器的位置使得被激光束照射到的挡板长度之和最大,你需要帮小 T 算出这 个最大值。

    输入输出格式

    输入格式:

    第一行包含一个正整数 T,表示测试数据的组数。

    对于每组测试数据,第一行是一个整数 $n$,表示挡板个数;
    接下来 n 行,每行包含四个整数 $x1, y1, x2, y2$,表示挡板的两端点分别是 $(x1, y1)$ 和 $(x2, y2)$,保证$(x1, y1){=}\mathllap{/\,}(x2, y2)$。
    第 $n + 2$ 行是五个整数 $x1, y1, x2, y2, L$,表示直线导轨经过了点 $(x1, y1)$ 和 $(x2, y2)$,且激光发射器的长度为 $L$,同样保证 $(x1, y1)\mathrlap{\,/}{=}(x2, y2)$。

    输出格式:

    对于每组测试数据,输出一行,包含一个实数,表示激光束能照射到的挡板长度之和的最大值,要求相对误差不超过 $10^{-6}$,也就是说,令输出结果为 $a$,标准答案为 $b$,若满足 $\dfrac{|a-b|}{max(1,b)}$ $≤$ $10^{-6}$,则输出结果会被认为是正确答案。

    输入输出样例

    输入样例#1: 复制
    3
    4
    -3 2 -1 2
    -1 -1 1 -1
    0 1 2 1
    2 -2 4 -2
    0 0 1 0 2
    4
    1 1 3 3
    2 1 4 2
    3 1 5 1
    3 -1 4 -1
    0 0 -1 0 2
    4
    -2 0 1 2
    1 3 -3 2
    1 -3 5 -1
    2 -1 4 3
    0 0 1 1 2
    
    输出样例#1: 复制
    3.000000000000000
    3.118033988749895
    4.251303782246768
    

    说明

    • $T ≤ 100$
    • $1 ≤ n ≤ 10^4$,
    • $1 ≤ L ≤ 2 × 10^9$,
    • 所有坐标的绝对值不超过 $10^9$。

    SubTasks

    • 子任务 1 (40 分):满足 $1 ≤ n ≤ 100$ 且所有坐标的绝对值不超过 $10^4$。
    • 子任务 2 (40 分):所有坐标的绝对值不超过 $10^6$。
    • 子任务 3 (20 分):没有任何附加的限制。
    提示
    标程仅供做题后或实在无思路时参考。
    请自觉、自律地使用该功能并请对自己的学习负责。
    如果发现恶意抄袭标程,将按照I类违反进行处理。