#1773. 共点圆

    ID: 1773 传统题 1000ms 256MiB 尝试: 0 已通过: 0 难度: NOI/NOI+/CTS 上传者: 标签>CTT赛事:contest136来源:qoj.ac数据:公开样例线段树平衡树

共点圆

共点圆

题目描述

标题: 共点圆 - Problem - QOJ.ac

#3684. 共点圆

Statistics

The problem was used in the following contests:

问题描述

在平面直角坐标系中,Wayne需要你完成 n 次操作,操作只有两种:

  1. 0 x y。表示在坐标系中加入一个以 (x,y) 为圆心且过原点的圆。
  2. 1 x y。表示询问点 (x,y) 是否在所有已加入的圆的内部(含圆周),且至少在一个圆内部(含圆周)。

为了减少你的工作量,题目保证圆心严格在 x 轴上方(纵坐标为正),且横坐标非零。

输入格式

第一行一个整数 n 。

接下来 n 行,每行第一个数是 0 或 1,分别表示两种操作。

接着有两个实数 x 和 y ,具体意义见题面。

输出格式

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

样例输入

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

样例输出

Yes
No

样例解释

如图,第一次询问时圆D并未加入,E在圆B和圆C内;第二次询问时E不在圆D内。

数据规模和约定

对于 30% 的数据,n≤1000;

对于 40% 的数据,输入数据可看作是不相关的随机数;

对于另外 20% 的数据,n≤100000,圆的交区域不会由多于 20 条圆弧组成;

对于另外 20% 的数据,第一次出现查询操作后不再加圆;

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

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

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

输入格式

(见题面原文)

输出格式

(见题面原文)

数据范围

(见题面原文)

样例

样例 1

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
Yes
No