P1766 液体滴落

    • 42通过
    • 212提交
  • 题目提供者 xudemin
  • 评测方式 云端评测
  • 标签 枚举,暴力 模拟 贪心
  • 难度 普及+/提高
  • 时空限制 1000ms / 128MB

题解

  • 提示:收藏到任务计划后,可在首页查看。
  • 最新讨论 显示

    推荐的相关题目 显示

    题目描述

    在平面中有若干线段Li(不一定互不相交)。组成一个又一个轨道,有一滴液体从上方滴落下来,如果碰到轨道就沿着轨道向下滚,从轨道较低的一端离开轨道,在轨道中不受任何影响,否则就垂直滴落,问最后液滴从什么位置落出整个系统。

    相信这个题目一定难不倒你。

    输入输出格式

    输入格式:

    第一行两个整数N和S,表示有N条线段,液滴从横坐标为S的地方落下。

    以下N行,每行四个整数xi1,yi1,xi2,yi2描述每条线段的端点位置。注意线段不包括两个端点,液体可以从一端点处滴下而不碰到斜面。

    输出格式:

    一行一个整数:表示最终液体落下的位置(横坐标)。

    输入输出样例

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

    说明

    对于50%的数据,1≤n≤100,-500≤x,y,S≤500;

    对于100%的数据,1≤n≤10,000,|x,y,S|≤1000,000,000.

    提示
    标程仅供做题后或实在无思路时参考。
    请自觉、自律地使用该功能并请对自己的学习负责。
    如果发现恶意抄袭标程,将按照I类违反进行处理。