Description

  在平面直角坐标系中,Wayne需要你完成n次操作,操作只有两种:
1.0 x y。表示在坐标系中加入一个以(x, y)为圆心且过原点的圆。
2.1 x y。表示询问点(x, y)是否在所有已加入的圆的内部(含圆周),且至少在一个圆内部(含圆周)。
为了减少你的工作量,题目保证圆心严格在x轴上方(纵坐标为正),且横坐标非零。

Input

  第1行一个整数n。
接下来n行,每行第一个数是0或1,分别表示两种操作。
接着有两个实数x和y,具体意义见题面。

Output

  对于每个询问操作,如果点在所有已加入的圆内(或圆周上),则输出“Yes”(不含引号);否则输出“No”(不含引号)。

Sample Input

5
0 2.0000 3.0000
0 4.0000 1.0000
1 1.000000 1.000000
0 -3.0000 2.0000
1 1.000000 1.000000

Sample Output

Yes
No

HINT

对于100%的数据,n≤500000,所有坐标绝对值不超过10000。

输入数据保证圆心纵坐标为正,横坐标非零。

圆心坐标保留4位小数,询问点坐标保留6位小数,请选手注意控制精度。

 

Source

中国国家队清华集训 2012-2013 第二天

满足条件的圆点不妨设为x0,y0 然后我每次询问的点不妨认为是x,y 那么显然满足一个条件$(x-x0)^{2}+(y-y0)^{2}<= x0^{2}+y0^{2}$ 通过化简可以得到$y0>=-\frac{x}{y}x0+\frac{x^{2}+y^{2}}{2*y}$ 或者$y0<=-\frac{x}{y}x0+\frac{x^{2}+y^{2}}{2*y}$所以我们一共需要维护两个凸包一个上凸 一个下凸每次我首先把所有询问的斜率排序 然后按照时间分治 每次先把时间靠前的扔前面 然后构造两个凸包 每次询问的时候 根据询问点的y的大小选择在某一个凸包上贰分一下 贰分出来的结果就是可以看图来想象 相当于我是这个凸包上多个半平面组成一个交 然后求一下我询问我的半平面交是否在询问直线的上方 在cdq的实现上还有一些细节 相当于我首先按照时间排序 然后做好之后 按照x排序方便我下一层排序 这就要求我们必须先分治左边 然后统计完这一层的答案再去分治右边才okay

 

分类: 几何cdq分治

elijahqi

辣鸡蒟蒻一枚qwq 欢迎加qq qwq 2922945330

发表评论

电子邮件地址不会被公开。 必填项已用*标注