tags:[圆の反演][乘法原理][尺取法]
题解:
圆の反演：将过O点的圆，映射成不过O的直线，相切的圆反演出来的直线平行。
我们将集合S中的点做反演变换：(x,y)->(x/(x^2+y^2), y/(x^2+y^2))
若OAB的外接圆与OCD的外接圆相切&&OAC外接圆与OBD外接圆相切。
那么反演后就有：A'B'//C'D' && A'C'//B'D'即A'B'C'D'为平行四边形
枚举所有的对角线，对于每一根对角线，我们记录下它的斜率，中点坐标。
对这些对角线排序后，使用尺取法&乘法原理即可。
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
using namespace std;
typedef long long LL;
const int MOD = 1000000000 + 7;
const int NICO = 1000 + 10;
int n, tot, ans;
double a,b,c,d,x,y;
struct Point
{
double x, y;
} p[NICO];
struct Mid
{
double x, y, k;
} mid[NICO*NICO];
bool equal(double x, double y)
{
return abs(x-y) < 1e-9;
}
bool cmp(Mid a, Mid b) //对所有对角线按中点横坐标，中点纵坐标，斜率三个关键字排序。
{
if(equal(a.x, b.x))
{
if(equal(a.y,b.y))
{
return a.k < b.k;
}
return a.y < b.y;
}
return a.x < b.x;
}
void read()
{
scanf("%d", &n);
for(int i=1;i<=n;i++)
{
scanf("%lf %lf %lf %lf",&a,&b,&c,&d);
x = a/b;
y = c/d;
p[i].x = x / (x*x + y*y); // 对所有点进行反演
p[i].y = y / (x*x + y*y);
}
}
void init() //求出对角线中点横坐标，中点纵坐标，斜率
{
for(int i=1;i<=n;i++)
{
for(int j=i+1;j<=n;j++)
{
mid[++tot].x = p[i].x + p[j].x;
mid[tot].y = p[i].y + p[j].y;
if(equal(p[i].x, p[j].x))
{
mid[tot].k = 1e9;
} else {
mid[tot].k = (p[j].y - p[i].y) / (p[j].x - p[i].x);
}
}
}
}
void solve()
{
sort(mid+1,mid+1+tot,cmp);
int i, j;
for(i=1;i<=tot;i=j) // 尺取法。
{
int cnt = 1; LL res = 1;
// 如果第j条线段中点的坐标与第i条线段中点的坐标不同，则跳出第二层循环。
for(j=i+1;j<=tot && equal(mid[j].x ,mid[i].x) && equal(mid[j].y, mid[i].y);j++)
{
if(equal(mid[j].k,mid[j-1].k)) cnt ++; // x,y,k皆相等！志同道合！
else res = res*(cnt+1)%MOD, cnt = 1; // 计数君阵亡！根据乘法原理，这些对角线有(cnt+1)种取法。
}
res = res * (cnt+1) % MOD;
ans = (ans + res - 1) % MOD;// 一根线段都不拿，会翻车！减掉！
}
printf("%d\n", ans - tot); // 只拿一根，会翻车！减掉！
}
int main()
{
read();
init();
solve();
}