#P3108. [USACO14OPEN] Cow Optics G

    ID: 2152 Type: RemoteJudge 1000ms 125MiB Tried: 0 Accepted: 0 Difficulty: 6 Uploaded By: Tags>贪心2014线段树USACO前缀和

[USACO14OPEN] Cow Optics G

题目背景

征求翻译。如果你能提供翻译或者题意简述,请直接发讨论,感谢你的贡献。

题目描述

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度。例如一个这样(“\“)的镜子可以把从下方射来的光线反射成向左的光线。

Bessie在启动激光的前一刻意识到计划有缺陷,所以她自己又拿着一面镜子出去了,恰好使得激光照到谷仓。

请计算Bessie可能站在的位置的总数。

坐标范围:-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 '/').

第一行:三个整数:N,Bx,By。

第2~N+1行:每行两个整数表示牛的位置,一个字符(”/“或"")表示镜子怎么放置的。

输出格式

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

Bessie所有可能站在的位置总数。

4 1 2 
-2 1 \ 
2 1 / 
2 2 \ 
-2 2 / 

2 

提示

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

样例中Bessie可能站在(0,1)或者(0,2)。

感谢@SystemLLH 提供翻译