P3508 [POI2010]LAT-Lamp

    • 0通过
    • 2提交
  • 题目提供者 洛谷
  • 评测方式 云端评测
  • 标签 线段树 计算几何 POI 2010 高性能
  • 难度 尚无评定
  • 时空限制 1000ms / 128MB


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

    推荐的相关题目 显示




    In the middle of the night Bitratio turned on the lamp at the entrance to the building that Byteasar lives in.

    Now the strong light prevents Byteasar from sleeping.

    While the lamp does not shine directly on Byteasar's windows, it does so by reflecting in other windows.

    Deprived of sleep, Byteasar is becoming irritated.

    To remedy that he tries to occupy his mind, but all he can think of is the light.

    Thus Byteasar looked out the window and wondered if his neighbours suffer similar torture, i.e., whether the light shines on their windows as well.

    Now that is an interesting question, at least in Byteasar's opinion.

    You learn of the puzzle sooner than you would wish: unable to solve the problem all by himself, thinking little of sleep now (be it his and yours), Byteasar calls you to ask for help.

    You know him well enough to understand that you too will not get any sleep until you write a program that solves his problem.

    Byteasar lives in the building , which has windows.

    The lamp is situated on a wall at the very bottom of this building.

    Opposite the building , exactly 10 meters apart, there is another building, .

    The wall of this -windowed building is parallel to the wall of , the Byteasar's building.

    The lamp light behaves like you would expect, i.e., in the way predicted by geometrical optics (or ray optics).

    Namely the light propagates along rays, and if a ray hits a window, it is reflected.

    Due to The Law of Reflection, the angle of the ray's reflection equals the angle of incidence.

    We introduce coordinate systems on the the walls of the two buildings in the following way.

    Both axes are horizontal, while both axes are vertical; the axes on both walls are identically oriented, and the points of the walls are opposite one another.

    The windows (on either building) are simply rectangles with sides parallel to the axes of the coordinate system.

    A ray is reflected only in the interior of any window; it is absorbed on the window's boundary.

    In each building, no two windows share any part of their interiors.

    The lamp is located on the wall of the building at the point , which is neither inside nor at the boundary of any window.



    In the first line of the standard input there are two integers and (), separated by a single space, denoting the number of windows in the first and second building respectively.

    The lines that follow describe the windows in Byteasar's building (the building), one per line.

    The line no. (for ) holds four integers , , , (, !…


    In the first line of the standard output your program should print the number of windows in the building whose interiors are hit by some ray.

    You may assume that in every test instance there will be at least one such window (the Byteasar's window).

    In the second line the numbers of these windows (windows are numbered starting from 1) should be printed in increasing order, separated by single spaces.


    输入样例#1: 复制
    3 3
    -1 2 1 4
    -1 5 1 7
    -3 8 -2 20
    -1 1 1 2
    -1 4 1 5
    -1 7 1 10
    输出样例#1: 复制
    1 2