P3122 [USACO15FEB]圈住牛Fencing the Herd

    • 6通过
    • 20提交
  • 题目提供者 FarmerJohn2
  • 评测方式 云端评测
  • 标签 凸包 计算几何 USACO 2015 高性能
  • 难度 省选/NOI-
  • 时空限制 1000ms / 128MB

题解

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

    推荐的相关题目 显示

    题目描述

    Farmer John needs your help deciding where to build a fence in the shape of a straight line to help restrict the movement of his cows. He has considered several possible fence locations and needs your help to determine which of these are usable, where a fence is considered usable if all of the cows are on the same side of the fence. A fence is not usable if there is a cow that lies directly on it. FJ will be asking you a number of queries regarding possible fence locations; a query should be answered "YES" if it corresponds to a usable fence location, "NO" otherwise.

    Additionally, FJ may occasionally bring new cows into the herd. When a new cow joins the herd, all fence queries from that point onward will require her to be on the same side of a fence as the rest of the herd for the fence to be usable.

    FJ需要你帮助他决定在哪里建造形状是一条无限长的直线的栅栏来限制他的牛的活动。他选出了几个可能的建造栅栏的位置,你需要帮助他判断哪些栅栏是有用的。一个栅栏是有用的当且仅当所有奶牛都在栅栏的同一侧(如果有牛群在栅栏所在的直线上,那么栅栏是没用的),FJ将会问你一些问题,如果这个栅栏是有用的,需要输出“YES”,反之输出“NO”。

    另外,FJ也可能会带来一些新的奶牛加入这个牛群。一头牛加入之后,以后的所有询问中,这头牛也需要与其它的牛在栅栏的同一侧。

    输入输出格式

    输入格式:

    The first line of input contains N (1 <= N <= 100,000) and Q (1 <= Q <= 100,000) separated by a space. These give the number of cows initially in the herd and the number of queries, respectively.

    The following N lines describe the initial state of the herd. Each line will contain two space separated integers x and y giving the position of a cow.

    The remaining Q lines contain queries either adding a new cow to the herd or testing a fence for usability. A line of the form "1 x y" means that a new cow has been added to the herd at position (x, y). A line of the form "2 A B C" indicates that FJ would like to test a fence described by the line Ax + By = C.

    All cow positions will be unique over the whole data set and will satisfy (-10^9 <= x, y <= 10^9). Additionally the fence queries will satisfy -10^9 <= A, B <= 10^9 and -10^18 <= C <= 10^18. No fence query will have A = B = 0.

    输出格式:

    For each fence query, output "YES" if the fence is usable. Otherwise output "NO".

    输入输出样例

    输入样例#1: 复制
    3 4 
    0 0 
    0 1 
    1 0 
    2 2 2 3 
    1 1 1 
    2 2 2 3 
    2 0 1 1 
    
    输出样例#1: 复制
    YES 
    NO 
    NO 
    
    

    说明

    The line 2x + 2y = 3 leaves the initial 3 cows on the same side. However the cow (1, 1) is on the other side of this fence making it no longer usable after she joins the herd. The line Y = 1 cannot be used because the cows (0, 1) and (1, 1) lie directly on it.

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