共点圆

共点圆(concurrent circles)平面几何术语.指多个圆的一种特殊位置关系.若干圆都通过同一个点称为共点圆。在同一圆周上的若干点称为共圆点，或称作这些点共圆。我们知道共圆点的种类有很多。大致可以分为三点共圆、四点共圆、多点共圆。

简介共点圆(concurrent circles)平面几何术语，指多个圆的一种特殊位置关系.若干圆都通过同一个点称为共点圆.如图1 , 有同一个公共点P，则是共点圆.又如图2设 ,分别是△ABC的顶点A,B,C在直线L上的射影，X,Y,Z分别是L上任一点P在BC,CA,AB上的射影，则OXYZ, OXB'C' , OYC'A' , OZA'B‘共点于Q.
通过与三角形有关的特定三个垂足点的圆.由一点向三角形每边所在直线作垂线，通过三垂足的圆称为该点对于三角形的垂足圆.例如图2中的OXYZ即点P对于△ABC的垂足圆.

求共点圆n次操作，每次加入一个以(x,y)为圆心，经过原点的圆，或者询问一个点是否在所有圆中（包括圆周）。

方法一：

设一个圆的圆心为(a,b)， 一个询问点为(x,y)，那么(x,y)在圆内或圆周上的条件是：

也就是说，若一个询问点在之前的所有圆中，那么对于每个圆心(a,b)都满足这条式子，而这个式子是一个明显的半平面形式，即问题变成了，每次加入圆的时候其实是加入一个圆心点，询问变成是否所有点都在一条直线的上方。我们对操作分治，变成每次把左边的点加进去，判断右边的询问是否满足。由于所有询问都是点在直线上方问题，所以我们可以对点维护下凸包，二分斜率，看看那一个点是否在下面即可。复杂度为O( ) 1。

方法二：

所有的圆都经过同一个点——原点！考虑圆反演，那么我们会得到很多直线，一个点在圆外也就是这个点反演后在直线的上方（这题中圆心都在x轴上方）。这样问题就变成了是否每个点都被所有半平面包含。这个可以通过求半平面交再三分，二分，或排序之类的得到。复杂度也为O()，但是询问的主体是不一样的 1。

本词条内容贡献者为:

王沛 - 副教授、副研究员 - 中国科学院工程热物理研究所