HDU4773 简单的圆的反演

08/23/2014

题意:给定相离的两个圆(圆心坐标以及半径)以及圆外的一个定点P,求出过点p的且与已知的两个圆外切的所有圆(输出总数+圆心、半径)。

 

应该是高中生们在准备自招是喜闻乐见的“阿波罗尼奥斯问题”13种情况中的一种较为特殊的情况中的一种较为特殊的情况。

( ·ω·、)窝们来分别使用{(x0,y0),(x1,y1,r1),(x2,y2,r2)}表示定点P与两个圆。

首先考虑最先想到的笔算解法:

联立方程组

{\sqrt{(x-x1)^2+(y-y1)^2}-\sqrt{(x-x0)^2+(y-y0)^2}=r1}

{\sqrt{(x-x2)^2+(y-y2)^2}-\sqrt{(x-x0)^2+(y-y0)^2}=r2}

这么奇怪的方程组用简短的代码在保证精度的情况下是比较难解决的,
所以我们考虑  开挂   反演!

在这里窝先来介绍一些比较简单、这道题目中会用到的反演结论姿势。(x1 因为我也只会这些比较简单的……

对于二维上的反演,我们通常是以一个圆 α {(x_{\alpha},y_{\alpha},r_{\alpha})} 为基础而进行的,我们称它的圆心为反演中心,半径为反演半径。

对于平面上与 圆α的圆心O  不同的一点A,与它的反演点A'满足如下关系:

{OA\cdot{}OA'=r^2}

不难发现,圆外的点对应的反演点处于圆内,圆内的反演点处于圆外,圆上的反演点依然是它自身,并且每个点有且仅有唯一的一个反演点(互为反演点)。

特殊地,反演中心没有反演点。

实际上,稍加推导我们即可得到对于这道题目而言相当实用的两个结论:

①不经过反演中心的直线,它的反形为经过反演中心的圆。

②不经过反演中心的圆,它的反形仍为一个圆,并且反演中心为这两个互为反形的圆的位似中心。

 

通过这两个结论,不难YY得到:

以点P为反演中心,不与已知两个圆相交的距离R为反演半径做反演圆,(建议设大一些,以防出现精度问题。)

分别做出{(x1,y1,r1),(x2,y2,r2)}的反演圆,

求出两个反演圆的公切线,

再将公切线反演变换回去,即可得到同时经过反演中心P、又与之前两个圆相切的圆。(因为唯一的交点反演回去仍旧是唯一的交点)。

 

思路已经理清楚了,现在来逐个步骤推倒:

①如何求反演圆:

设两个关于{(O,r)}反演的圆为{(C1?r1),(C2,r2)}

则可以根据反演关系列出如下式子:

{(OC1+r1)\cdot{}(OC2-r2)=r^2}

{(OC1-r1)\cdot{}(OC2+r2)=r^2}

若我们已知C1与r1、r,则不难求出:

{r2=\frac{1}{2}(\frac{1}{OC1-r1}-\frac{1}{OC1+r1})r^2}

{x2=x0+\frac{OC2}{OC1}(x1-x0)}

{y2=y0+\frac{OC2}{OC1}(y1-y0)}

如此即可在已知原圆与反演中心、半径的时候求出原圆的反演圆。

 

②求两个圆的公切线

这道题目只需求外公切线即可(x2 外婆切线【

我们可以通过在大圆内构造同心,半径为(R-r)的辅助圆。

可以发现“过小圆圆心”的辅助员切线是与外公切线平行的。

如此即可方便的计算啦。