QOJ.ac

QOJ

Time Limit: 3 s Memory Limit: 256 MB Total points: 100

#3684. 共点圆

Statistics

问题描述

在平面直角坐标系中,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

样例解释

problem_3684_1.png

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

数据规模和约定

对于 $30\%$ 的数据,$n \leq 1\,000$;

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

对于另外 $20\%$ 的数据,$n \leq 100\,000$,圆的交区域不会由多于 $20$ 条圆弧组成;

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

对于 $100\%$ 的数据,$n\leq 500\,000$,所有坐标绝对值不超过 $10\,000$。

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

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

Discussions

About Discussions

The discussion section is only for posting: Editorials, General Discussions (problem-solving strategies, alternative approaches), and Off-topic conversations.

This is NOT for reporting issues! If you want to report bugs or errors, please use the Issues section below.

Open Discussions 0
No discussions in this category.

Issues

About Issues

If you find any issues with the problem (statement, scoring, time/memory limits, test cases, etc.), you may submit an issue here. A problem moderator will review your issue.

Guidelines:

  1. This is not a place to publish discussions, editorials, or requests to debug your code. Issues are only visible to you and problem moderators.
  2. Do not submit duplicated issues. Submitting multiple issues may cause your account to be banned.
  3. Issues must be filed in English or Chinese only.
Active Issues 0
No issues in this category.
Closed/Resolved Issues 0
No issues in this category.