引入反演
定义反演中心为点P 任意值为反演半径R(有时需要考虑精度问题选取适当值)反演后的图形为反形
则对平面上任意一点A都有反演点A’ PAPA’=RR
对于圆的反演
1.过中心的圆的反形一条不过中心的直线
2.不过中心的一条直线的反形是一个过中心的圆(与上一条相反)
3.不过中心的圆的反形仍然是一个圆
4.反演前后相切关系和平行关系不变
Mindis hdu 6097
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
int i, j, k, n, m, s, t;
const double zero = 1e-8;
double R;
struct node {
double x, y;
void in() {
scanf("%lf %lf", &x, &y);
}
} a, b;
double sqr(const double &x) {
return x * x;
}
double dist(const node &x, const node &y) {
return sqrt(sqr(x.x - y.x) + sqr(x.y - y.y));
}
node moveit(const node &p, const double &a, const double &d) {
return (node){p.x + d * cos(a), p.y + d * sin(a)};
}
node inversion(const node &x) {//对点做反演
double d = sqr(R) / dist((node){0, 0}, x);
double a = atan2(x.y, x.x);
return moveit((node){0, 0}, a, d);
}
double cross(const node &x, const node &y) {
return y.y * x.x - x.y * y.x;
}
int sign(const double &x) {
if (fabs(x) < zero) {
return 0;
} else if (x > 0) {
return 1;
} else {
return -1;
}
}
double getdist(const node &x, const node &y) {
double L = dist(x, y);
if (fabs(L) == 0) {//两点重合 返回两倍该点到圆心(0,0)的距离
return 2.0 * (dist((node){0, 0}, x) - R);
}
double d = fabs(cross(x, y)) / L;// cross 返回 三角形xyo的面积 L为斜边 xy的长度 d为三角形在L的高
if (sign(R - d) != -1) {//有交点
return L;
} else {//无交点
return 2.0 * sqrt(sqr(L / 2) + sqr(d - R));
}
}
int main() {
int T;
scanf("%d", &T);
while (T--)
{
scanf("%lf", &R);
a.in(), b.in();
double t = dist((node){0, 0}, a);
if (sign(t) != 1) {
printf("%.8f\n", 2.0 * R);
continue;
}
t = dist((node){0, 0}, a) / R;//相似的比
a = inversion(a);
b = inversion(b);
printf("%.8f\n", getdist(a, b) * t);
}
return 0;
}
The Designer hdu 6158
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const double pi = acos(-1);
const double zero = 1e-14;
int i, j, k, n, m, s, t;
double r1, r2, R, x1, x2, ans, r;
struct node {
double x, y;
} p;
struct circle {
node o;
double r;
} now;
double sqr(const double &x) {
return x * x;
}
int sign(const double &x) {
if (fabs(x) < zero) {
return 0;
} else if (x > 0) {
return 1;
} else {
return -1;
}
}
double dist(const node &x, const node &y) {
return sqrt(sqr(x.x - y.x) + sqr(x.y - y.y));
}
circle inversion(const node &p, const double &r) {
circle res;
res.r = r / (sqr(dist(p, (node){0, 0})) - sqr(r)) * sqr(R);
res.o = (node){0, 0};
return res;
}
int main() {
R = 20.0;//按照半径20来反演
int T;
scanf("%d", &T);
while (T--)
{
scanf("%lf %lf", &r1, &r2);//两个大圆的半径
if (r1 < r2) {// r2 为大圆
swap(r1, r2);
}
scanf("%d", &n);//加几个圆
x1 = sqr(R) / (2.0 * r1);//反演后的直线 x = x1;
x2 = sqr(R) / (2.0 * r2);//反演后的直线 x = x2;
r = (x2 - x1) / 2.0;//反演后形成圆的半径
p = (node){(x1 + x2) / 2.0 , 0};//反演后圆的位置
now = inversion(p, r);//将当前的圆反演回去
ans = pi * sqr(now.r);//反演回去的圆的面积
for (int i = 2; i <= n; i++) {
if ((i & 1) == 0) {//每逢 2 反演后的圆的面积就要改变
p.y += 2.0 * r;
now = inversion(p, r);
}
ans += pi * sqr(now.r);
if (sign(pi * sqr(now.r)) != 1) {//当圆足够小时 就停止
break;
}
}
printf("%.5f\n", ans);
}
return 0;
}
Problem of Apollonius hdu 4773
#include <cstdio>
#include <algorithm>
#define dd double
#define eps 1e-10
using namespace std;
dd sqr(dd x){return x*x;}
struct cir{
dd x,y,r;
cir(dd _x=0,dd _y=0,dd _r=0):x(_x),y(_y),r(_r){}
void in(int t){scanf("%lf%lf",&x,&y);if(t)scanf("%lf",&r);}
void out(){printf("%f %f %f\n",x,y,r);}
cir point(dd a){//以圆心为原点,a为极角,对应的圆上的点。
return cir(x+r*cos(a),y+r*sin(a));
}
}p,c1,c2,st[5],ed[5];
int cnt;
dd xmult(cir a,cir b,cir o){//向量 ao 和向量 bo的叉积
return (a.x-o.x)*(b.y-o.y)-(a.y-o.y)*(b.x-o.x);
}
dd dis(cir a,cir b,cir c){//点 c 到直线 ab 之间的距离
dd A=b.y-a.y,B=a.x-b.x,C=b.x*a.y-b.y*a.x;
return fabs(A*c.x+B*c.y+C)/sqrt(sqr(A)+sqr(B));
}
dd dis(cir a,cir b){//圆心之间的距离
return sqrt(sqr(a.x-b.x)+sqr(a.y-b.y));
}
cir cross(dd a1,dd b1,dd c1,dd a2,dd b2,dd c2){//a1X+b1Y+c1=0和a2X+b2Y+c2=0的交点
dd y=-c1/b1;
if(a1==0)return cir((-c2-b2*y)/a2,y);
y=(a2*c1/a1-c2)/(b2-b1*a2/a1);
return cir(-(c1+b1*y)/a1,y);
}
void inv(cir &c){//圆c反演变换
dd d=dis(c,p),s=sqr(p.r)/(d-c.r),t=sqr(p.r)/(d+c.r);
c.r=(s-t)/2;
c.x=p.x+(c.x-p.x)/d*(t+c.r);
c.y=p.y+(c.y-p.y)/d*(t+c.r);
}
cir inv(cir a,cir b){//直线ab的反演
dd a1=b.y-a.y,b1=a.x-b.x,c1=a.y*b.x-a.x*b.y;//直线ab写成a1X+b1Y+c=0的形式
cir cr=cross(a1,b1,c1,b1,-a1,a1*p.y-b1*p.x);//p到直线ab的垂足
dd r=sqr(p.r)/dis(a,b,p)/2,d=dis(cr,p);
return cir(p.x+r/d*(cr.x-p.x),p.y+r/d*(cr.y-p.y),r);
}
int sgn(dd a){//精度误差
return (a>eps)-(a<-eps);
}
bool sameside(cir a,cir b,cir s,cir t){
return sgn(xmult(s,t,a))==sgn(xmult(s,t,b));//利用叉积判断是否在直线同侧
}
void tangent(cir a,cir b)//求圆 a 和圆 b的公切线
{
cnt=0;
dd base=atan2(b.y-a.y,b.x-a.x),d=dis(a,b),ang=acos((a.r-b.r)/d);
//这里因为写成a.y-b.y,a.x-b.x而wa了,画了下图就明白了
st[cnt]=a.point(base-ang),ed[cnt]=b.point(base-ang);
if(sameside(p,a,st[cnt],ed[cnt]))cnt++;//p和圆心在切线的同侧
st[cnt]=a.point(base+ang),ed[cnt]=b.point(base+ang);
if(sameside(p,a,st[cnt],ed[cnt]))cnt++;
}
int main(){
int t;
scanf("%d",&t);
while(t--){
c1.in(1);c2.in(1);p.in(0);p.r=1;
inv(c1);inv(c2);//c1,c2关于p反演
tangent(c1,c2);//求外公切线
printf("%d\n",cnt);
for(int i=0;i<cnt;i++)inv(st[i],ed[i]).out();//外公切线关于p反演后的圆
}
return 0;
}
2019 ICPC沈阳区域赛 E Capture Stars
#include<bits/stdc++.h>
using namespace std;
typedef double db;
const double eps = 1e-8;
int sign(db k){
if (k>eps) return 1; else if (k<-eps) return -1; return 0;
}
int main()
{
int T;
scanf("%d",&T);
while(T--)
{
int n;
db R,r;
scanf("%d%lf%lf",&n,&R,&r); //x1=2R,x2=2R*R/r
db mid=R+R*R/r;//相切圆的 x
db RR=R*R/r-R;//相切圆的半径
vector<pair<db,int> > v;
v.clear();
for(int i=1;i<=n;i++)
{
db xx,yy;
scanf("%lf%lf",&xx,&yy);
//反演的点坐标
db x=4*R*R*xx/(xx*xx+yy*yy);
db y=4*R*R*yy/(xx*xx+yy*yy);
db hh=sqrt(RR*RR-(mid-x)*(mid-x));
v.push_back(make_pair(y-hh,1));//上半圆交点
v.push_back(make_pair(y+hh,-1));//下半圆交点
}
sort(v.begin(),v.end());//对纵坐标排序
int ans=0,cnt=0;
for(int i=0;i<2*n;i++)
{
cnt+=v[i].second;
ans=max(ans,cnt);
}
printf("%d\n",ans);
}
return 0;
}