Codeforces372E Drawing Circles is Fun【圆的反演】

题目描述：

平面n个点，原点O(0,0)，不存在$P_i,P_j$满足$P_{i}O{P}_j$三点共线。 求一种集合的个数：$(P_1,P_2)(P_3,P_4)...(P_{2k-1},P_{2k})$（无序） 使得：

$k\ge 2，P_i\ne P_j$对$\forall i\ne j$，满足$△O{P}_{2i-1}{P}_{2j-1}$的外接圆与$△O{P}_{2i}{P}_{2j}$的外接圆只有一个交点，$△O{P}_{2i}{P}_{2j-1}$的外接圆与$△O{P}_{2i-1}{P}_{2j}$的外接圆只有一个交点。

题目分析：

一个交点，想一想可以看出应该是圆心在一条直线上，可是并没有什么用，因为并不能快速求出所有点对的外接圆圆心以及判断是否在一条线上。

做这道题前需要先学习一波圆的反演：ACdreamers，NineSwords，Dance Of Faith 反演变换的几何证明 再结合GeoGebra画画图（有反演功能）应该就可以大概理解了。 反演圆的半径 $r_2=\frac{r_1\ast r^2}{d_1^2-r_1^2}$，原象和反象是位似的。

对于这道题，将圆反演后只有一个交点就变为了两条直线平行，将每个点反演后的点记为$A_i$，问题则变为对$\forall i\ne j$，满足$A_{2i-1}{A}_{2j-1}\parallel A_{2i}{A}_{2j}$且$A_{2i}{A}_{2j-1}\parallel A_{2i-1}{A}_{2j}$。发现$A_{2i-1}{A}_{2i}{A}_{2j-1}{A}_{2j}$是平行四边形，而平行四边形对顶点的中点相同，所以我们可以枚举点对然后记录它们反演后的中点和直线斜率（外接圆相同时斜率相同，但是不符合条件，斜率不同才可以计算），分开计算每个中点的答案然后乘起来即可，注意中点相同斜率相同的只能取一个。

Code：

#include<bits/stdc++.h> #define maxn 1005 using namespace std; const double eps = 1e-9; const int mod = 1e9+7; int n,m,ans; inline int sgn(double x){return (x>eps)-(x<-eps);} struct Point{ double x,y; Point(){} Point(double x,double y):x(x),y(y){} Point operator + (Point p)const{return Point(x+p.x,y+p.y);} Point operator * (double t)const{return Point(x*t,y*t);} }p[maxn]; struct node{ double x,y,k; bool operator < (const node &p)const{return sgn(x-p.x)?x<p.x:sgn(y-p.y)?y<p.y:k<p.k;} }M[maxn*maxn]; int main() { scanf("%d",&n); for(int i=1,a,b,c,d;i<=n;i++){ scanf("%d%d%d%d",&a,&b,&c,&d),p[i]=Point(1.*a/b,1.*c/d); p[i]=p[i]*(1/(p[i].x*p[i].x+p[i].y*p[i].y)); } for(int i=1;i<n;i++) for(int j=i+1;j<=n;j++) M[++m]=(node){(p[i].x+p[j].x)*0.5,(p[i].y+p[j].y)*0.5,sgn(p[i].x-p[j].x)?(p[i].y-p[j].y)/(p[i].x-p[j].x):1e9}; sort(M+1,M+1+m); for(int i=1,j;i<=m;i=j){ int cnt=1,ret=1; for(j=i+1;j<=m&&!sgn(M[j].x-M[i].x)&&!sgn(M[j].y-M[i].y);j++) if(!sgn(M[j].k-M[j-1].k)) cnt++; else ret=1ll*ret*(cnt+1)%mod,cnt=1;//cnt记录中点和斜率都相同的点对数目，每一组可以不选 ret=1ll*ret*(cnt+1)%mod; ans=(ans+ret-1)%mod;//可以不选这个中点 } printf("%d\n",(ans-m+mod)%mod);//可能只选了一个点对 }

​ .