P3108 [USACO14OPEN]牛光学Cow Optics

    • 4通过
    • 14提交
  • 题目提供者 FarmerJohn2
  • 评测方式 云端评测
  • 标签 前缀和 线段树 贪心 USACO 2014 高性能
  • 难度 尚无评定
  • 时空限制 1000ms / 128MB


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

    推荐的相关题目 显示




    Farmer John's cows would like to host a dance party in their barn, complete with a laser light show. Unfortunately, the only working laser they have found is located far away from the barn and too heavy to move, so they plan to re-direct the laser light to the barn using a series of mirrors.

    The layout of the farm has the laser at position (0,0) pointing north (in the positive y direction), and the barn at (Bx, By); we can think of both the laser and the barn as points in the 2D plane. There are already N cows (1 <= N <= 100,000) scattered throughout the farm holding mirrors that are aligned at angles of 45 degrees to the axes. For example, a mirror aligned like \ will take a beam of light entering from below and reflect it to the left. We can also think of the mirrors as being located at points in the 2D plane.

    Just before pressing the big red button to activate the laser, Bessie noticed a major flaw in the plan: the laser cannot hit the barn with the mirrors in their current configuration! As a result, she plans to run out onto the field, and hold up one more mirror (placed once again at a 45 degree angle) in order to redirect the laser onto the barn. Please count the number of locations in the field where Bessie can stand to accomplish this goal.

    All coordinates are integers between -1,000,000,000 and 1,000,000,000. It is guaranteed that any mirrors to be placed will be in this range as well. The cows running the laser insist that the beam should never come back to (0,0) after leaving this location (and with the mirrors in their initial configuration, it is guaranteed that this will not happen). No two cows occupy the same point in space, and Bessie cannot locate herself at the same position as an existing cow.


    激光的位置在(0,0),指向为北方(即y轴正方向),谷仓在位置(Bx,By)。已经有N头奶牛拿着镜子分散在农场的各个位置(1 <= N <= 100,000),镜子与原点之间的夹角为45度。例如一个这样(“\“)的镜子可以把从下方射来的光线反射成向左的光线。



    坐标范围:-1,000,000,000 到 1,000,000,000,数据保证初始时激光光束不会反射回(0,0)位置。同一点上不可能有多头牛,Bessie不能站在其他牛的位置。



    * Line 1: The integers N, Bx, and By.

    * Lines 2..N + 1: Line i+1 describes the ith mirror with 3 elements: its (x,y) location, and its orientation (either '\' or '/').




    where Bessie can stand to redirect the laser to the barn.



    输入样例#1: 复制
    4 1 2 
    -2 1 \ 
    2 1 / 
    2 2 \ 
    -2 2 / 
    输出样例#1: 复制


    A mirror at (0,1) or (0,2) placed in either direction would do the trick.


    感谢@SystemLLH 提供翻译