QOJ.ac

QOJ

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

#3684. 共点圆

统计

问题描述

在平面直角坐标系中,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$ 位小数,请选手注意控制精度。

About Issues

We understand that our problem archive is not perfect. If you find any issues with the problem, including the statement, scoring configuration, time/memory limits, test cases, etc.

You may use this form to submit an issue regarding the problem. A problem moderator will review your issue and proceed it properly.

STOP! Before you submit an issue, please READ the following guidelines:

  1. This is not a place to publish a discussion, editorial, or requests to debug your code. Your issue will only be visible by you and problem moderators. Other users will not be able to view or reply your issues.
  2. Do not submit duplicated issues. If you have already submitted one, please wait for an moderator to review it. Submitting multiple issues will not speed up the review process and might cause your account to be banned.
  3. Issues must be filed in English or Chinese only.
  4. Be sure your issue is related to this problem. If you need to submit an issue regarding another problem, contest, category, etc., you should submit it to the corresponding page.

Active Issues 0

No issues in this category.

Closed/Resolved Issues 0

No issues in this category.