精华内容
下载资源
问答
  • 反演变换

    千次阅读 2017-10-04 22:17:12
    反演变换基本概念 定义 : 对于平面上的一点 O 和一个非零常数 k ,使得平面上任何一个异于 O 点的 A 与 A’ 存在以下关系 : A O A‘三点共线; OA * OA’ = k ,则这个变换称为平面的一个...

    高中数学竞赛用过这种东西,但是大学一年没碰全忘了 …. emmmm…. 最近感觉大家都在用圆的反演变换 出 计算几何的 题 ,那就 …. 再学一遍吧

    反演变换基本概念

    1. 定义 : 对于平面上的一点 O 和一个非零常数 k ,使得平面上任何一个异于 O 点的 A 与 A’ 存在以下关系 :
      1. A O A‘三点共线;
      2. OA * OA’ = k
        ,则这个变换称为平面的一个反演变换,记做I(O,k).其中,定点O称为 反演中心,常数k称为反演幂,点’ A称为点A的反点.
    2. 若在这种变换下 一个图形 F 变成了图形 F’,则成两个图形互为反形,若反演之后点的位置不发生变化,则称这个点为自反点,如果图形也不发生变换的话则称这个图形为自反图形。
    3. 设两条曲线u,v、相交于点A,l、m分别是曲线u,v、在点A处的切线(如果存在),则l与m的交角称为曲线u,v、在点A处的交角;如果两切线重合,则曲线u,v、在点A处的交角为0.特别地,如果两圆交于点,那么过点作两圆的切线,则切线的交角称为两圆的交角.当两圆的交角为90 时,称为两圆正交;如果直线与圆相交,那么过交点作圆的切线,则切线与直线的交角就是直线与圆的交角.当这个交角为90 时,称为直线与圆正交


    反演的性质 :

    1. 定理1. 在反演变换下,不共线的两对互反点是共圆的四点.
    2. 定理2. 在反演变换I(0,k)下,设AB、两点(均不同于反演中心O)的反点分别为 A’B’ 则有’A’B’ = | k| * |AB| / (OA * OB )
    3. . 定理3. 在反演变换下,过反演中心的直线不变
    4. . 定理4. 在反演变换下,不过反演中心的直线的反形是过反演中心的圆;过反演中心的圆的反形是不过反演中心的直线.

    性质的证明用到的都是基本的三角形相似和最基础的四点共圆 如果想证的快的话,最好知道一些圆幂定理。

    反演一般来说经常用在圆中,因为可以把圆的关系转化到直线的关系上去做,多个圆的时候更能体现出这种优势。

    展开全文
  • HDU 4773 反演变换

    2017-10-05 16:04:37
    为什么能想到反演,关键就在于这个题的p 是圆上的一点,这就说明这个题目可能用反演去进行变换了。任意规定反演半径和反演基圆(但是要注意精度)然后把两个圆反演出去 (根据结论 不过反演中心的圆反演后还是圆,...

    为什么能想到反演,关键就在于这个题的p 是圆上的一点,这就说明这个题目可能用反演去进行变换了。任意规定反演半径和反演基圆(但是要注意精度)然后把两个圆反演出去 (根据结论 不过反演中心的圆反演后还是圆,反演中心是他们的一个位似中心) 然后再求外公切线 (因外题目要求是外切),再把得到的直线反演回来就可以了。

    #include<cmath>
    #include<cstdio>
    #include<cstdlib>
    #include<cstring>
    #include<algorithm>
    using namespace std;
    typedef long long ll;
    
    const double eps = 1e-10;
    
    class Point{
    public:
        double x,y;
        Point(double _x=0,double _y=0):x(_x),y(_y){}
        Point operator + (Point  rhs){return Point(x+rhs.x,y+rhs.y);}
        Point operator - (Point  rhs){return Point(x-rhs.x,y-rhs.y);}
        Point operator * (double rhs){return Point(x*rhs,y*rhs);}
        Point operator / (double rhs){return Point(x/rhs,y/rhs);}
        Point Move(double a,double d){return Point(x+d*cos(a),y+d*sin(a));}
        void Read(){scanf("%lf%lf",&x,&y);}
    }P;
    
    class Circle{
    public:
        Point o;double r;
        Circle(double _x=0,double _y=0,double _r=0):o(_x,_y),r(_r){}
        void Read(){o.Read();scanf("%lf",&r);}
        void out(){printf("%.8f %.8f %.8f\n",o.x,o.y,r);}
    }c[5];
    
    int Sign(double x){return (x>eps) - (x<-eps);}
    double Cross(Point a,Point b,Point c){return (b.x-a.x)*(c.y-a.y) - (c.x-a.x)*(b.y-a.y);}
    double Dis(Point a,Point b){return sqrt((a.x-b.x)*(a.x-b.x) + (a.y-b.y)*(a.y-b.y));}
    double R;
    int tot;
    
    Circle Inverse(Circle a){
        Circle res;
        double oc1 = Dis(P,a.o);
        double k1 = 1.0 / (oc1 - a.r);
        double k2 = 1.0 / (oc1 + a.r);
        res.r = 0.5*(k1 - k2)*R*R;
        double oc2 = 0.5*(k1 + k2)*R*R;
        res.o =P + (a.o - P)*oc2 / oc1;
        return res;
    }
    
    void Mark(Point a,Point b){
        ++tot;
        double tem = fabs(Cross(a,P,b)/Dis(a,b))*2.0;
        c[tot].r = R*R/tem;
        double d = Dis(a,c[0].o);
        c[tot].o = P + (a-c[0].o)*(c[tot].r/d);
    }
    
    void solve(){
        for(int i=0 ;i<2 ;i++) c[i] = Inverse(c[i]);
        if(c[0].r < c[1].r) swap(c[0],c[1]);
        Point tem = c[1].o - c[0].o;
        double a1 = atan2(tem.y,tem.x);
        double a2 = acos((c[0].r - c[1].r)/Dis(c[0].o,c[1].o));
        Point P1 = c[0].o.Move(a1+a2,c[0].r);
        Point P2 = c[1].o.Move(a1+a2,c[1].r);
        if(Sign(Cross(P1,c[0].o,P2)) == Sign(Cross(P1,P,P2))) Mark(P1,P2);
        P1 = c[0].o.Move(a1-a2,c[0].r);
        P2 = c[1].o.Move(a1-a2,c[1].r);
        if(Sign(Cross(P1,c[0].o,P2)) == Sign(Cross(P1,P,P2))) Mark(P1,P2);
    }
    
    int main(){
        R = 5.0; //保证精度的前提下任意取的反演半径
        int T;scanf("%d",&T);
        while(T--){
            tot = 1;
            for(int i=0 ;i<2 ;i++) c[i].Read();
            P.Read();
            solve();
            printf("%d\n",tot-1);
            for(int i=2 ;i<=tot ;i++) c[i].out();
        }
        return 0;
    }
    展开全文
  • 题目大意:给两个相离的圆和一个不在圆上的点O,问经过该点且与两个圆都外切的圆有哪些。解题思路:这个blog解释的挺不错: ... 不过本蒟蒻还是理一下自己的思路。首先了解一下反演的定义: 设反演中心为OO,反演半径...

    题目大意:

    给两个相离的圆和一个不在圆上的点O,问经过该点且与两个圆都外切的圆有哪些。

    解题思路:

    这个blog解释的挺不错:
    http://blog.csdn.net/acdreamers/article/details/16966369
    不过本蒟蒻还是理一下自己的思路。

    首先了解一下反演的定义:
    设反演中心为O,反演半径为R,那么若有两点P,P连线过O点,且OPOP=R2,则称PP关于O互为反演
    这个定义可推广到任意图形上。

    然后就是反演的性质了。
    1、不经过O的直线反演后成为一个经过O的圆
    2、经过O的圆,反演后成为不经过O的一条直线
    2、不经过O的圆,反演后成为另一个圆,且两个圆关于O位似
    4、过O的直线反演后不变
    5、反演不改变相切性

    那再来看看本题。

    由于直接求圆难度很大,但求两个圆的公切线较简单(其实也挺麻烦,全靠画图yy),所以我们可以先求两个圆关于O点的反演(反演半径随便),再求反演后两个圆的公切线,再将公切线关于O反演回来,根据性质1和5,就得到与原来两个圆相切的圆了。

    注意题目要求的是都外切,所以所求切线需在反演后两圆圆心及O点同侧(画画图就知道啦,其他情况的切线分别对应都内切及一内一外的情况)。

    #include<cstdio>
    #include<iostream>
    #include<cstring>
    #include<string>
    #include<algorithm>
    #include<cmath>
    #include<ctime>
    #include<vector>
    #include<set>
    using namespace std;
    
    int getint()
    {
        int i=0,f=1;char c;
        for(c=getchar();(c!='-')&&(c<'0'||c>'9');c=getchar());
        if(c=='-')f=-1,c=getchar();
        for(;c>='0'&&c<='9';c=getchar())i=(i<<3)+(i<<1)+c-'0';
        return i*f;
    }
    
    
    const double R=1,eps=1e-11;
    struct point
    {
        double x,y;
        point(){}
        point(double _x,double _y):
            x(_x),y(_y){}
        inline friend point operator + (const point &a,const point &b)
        {return point(a.x+b.x,a.y+b.y);}
        inline friend point operator - (const point &a,const point &b)
        {return point(a.x-b.x,a.y-b.y);}
        inline friend point operator * (const point &a,double b)
        {return point(a.x*b,a.y*b);}
        inline friend double operator * (const point &a,const point &b)
        {return a.x*b.x+a.y*b.y;}
        inline friend double cross(const point &a,const point &b)
        {return a.x*b.y-a.y*b.x;} 
        inline  point n(){return point(-y,x);}
        inline double dis(){return sqrt(x*x+y*y);}
    }O;
    struct circle
    {
        point O;double r;
    }C1,C2,C3,C4,C5,C6;
    struct line
    {
        point st,ed;
    }l1,l2;
    int bz1,bz2;
    
    double Pow(double x)
    {
        return x*x;
    }
    
    void getline()
    {
        if(C3.r==C4.r)
        {
            point t=(C4.O-C3.O).n();
            t=t*(1/t.dis());
            l1.st=C3.O+t*C3.r,l1.ed=C4.O+t*C4.r;
            l2.st=C3.O-t*C3.r,l2.ed=C4.O-t*C4.r;
        }
        else
        {
            l1.st=l2.st=C3.O+(C3.O-C4.O)*(C3.r/(C4.r-C3.r));
            point t=C3.O-l1.st;
            double Sin=C3.r/t.dis(),d=C3.r*Sin;
            t=t*(1/t.dis());
            l1.ed=l2.ed=C3.O-t*d;
            t=t.n(),d=sqrt(Pow(C3.r)-Pow(d));
            l1.ed=l1.ed+t*d,l2.ed=l2.ed-t*d;
        }
    }
    
    point getcross(line a,line b)
    {
        double x=cross(a.ed-a.st,b.st-a.st);
        double y=cross(b.ed-a.st,a.ed-a.st);
        point t=b.st+(b.ed-b.st)*(x/(x+y));
        return t;
    }
    
    void solve(line a,circle &C,int &bz)
    {
        if(abs(cross(a.ed-O,a.st-O))<eps)return;
        line b;
        b.st=O;b.ed=O+((a.ed-a.st).n());
        point p=getcross(a,b);
        if((O-p)*(C3.O-p)<0)return;
        bz=1;
        point t=p-O;t=t*(1/t.dis());
        C.r=Pow(R)/(p-O).dis()*0.5;
        C.O=O+t*C.r;
    }
    
    int main()
    {
        //freopen("lx.in","r",stdin);
        //freopen("lx.out","w",stdout);
        int T=getint();
        while(T--)
        {
            bz1=bz2=0;
            C1.O.x=getint(),C1.O.y=getint(),C1.r=getint();
            C2.O.x=getint(),C2.O.y=getint(),C2.r=getint();
            O.x=getint(),O.y=getint();
            C3.r=Pow(R)*C1.r/(Pow((O-C1.O).dis())-Pow(C1.r));
            C3.O=O+(C1.O-O)*((Pow(R)/((C1.O-O).dis()+C1.r)+C3.r)/(C1.O-O).dis());
            C4.r=Pow(R)*C2.r/(Pow((O-C2.O).dis())-Pow(C2.r));
            C4.O=O+(C2.O-O)*((Pow(R)/((C2.O-O).dis()+C2.r)+C4.r)/(C2.O-O).dis());
            if(C3.r>C4.r)swap(C3,C4);
            getline();
            solve(l1,C5,bz1);
            solve(l2,C6,bz2);
            printf("%d\n",bz1+bz2);
            if(bz1)printf("%.8f %.8f %.8f\n",C5.O.x,C5.O.y,C5.r);
            if(bz2)printf("%.8f %.8f %.8f\n",C6.O.x,C6.O.y,C6.r);
        }
        return 0;
    }
    展开全文
  • 题目大意:给你一个圆和圆内到圆心距离相等的两点 P Q ,让你在圆上找到一个点 K ,使得这 PK + QK 最小。

    题目大意:

    给你一个圆和圆内到圆心距离相等的两点 P Q ,让你在圆上找到一个点 K ,使得这 PK + QK 最小。

    分析:

    学到一个几何方面的知识,这么好用的东西之前我居然没听说过,叫做反演。就是在OP的延长线上,取A,使得 OAOP=r2 。从而构造出相似三角形。

    未AC代码:

    #include<bits/stdc++.h>
    
    using namespace std;
    
    double r,px,py,qx,qy,ax,ay,bx,by;
    int test;
    
    int main()
    {
        scanf("%d",&test);
        while(test--)
        {
            scanf("%lf%lf%lf%lf%lf",&r,&px,&py,&qx,&qy);
            double op,oq,pq;
            op=sqrt(px*px+py*py);
            oq=op;
            pq=sqrt((px-qx)*(px-qx)+(py-qy)*(py-qy));
            if(op+oq-pq<1e-9)
            {
                double ans=2.0*sqrt(op*op+r*r);
                printf("%.7f\n",ans);
                continue;
            }
            double oa=r*r/op;
            double c=(op*op+oq*oq-pq*pq)/(2.0*op*oq);
            double cc=sqrt((c+1)/2.0);
            //cout<<cc<<endl;
            /*if(cc<=1e-6)
            {
                double ans=oa/r/pq;
                //cout<<1;
                printf("%lf\n",ans);
                continue;
            }*/
            double dis=oa*cc;
            if(dis>r)
            {
                double x=sqrt(op*op+r*r-cc*2.0*op*r);
                double ans=2*x;
                printf("%.7f\n",ans);
                //cout<<"dsa";
            }
            else
            {
                double ans=pq*r/op;
                printf("%.7f\n",ans);
            }-
        }
    
    }

    样例已过,精度或边界问题。

    展开全文
  • 本题就是先把给定的两个圆(O1, O2)经过一次反演变换得到新的圆(O3, O4),然后求O3,O4的外公切线(L),显然此时若把L和O3,O4都经过一次反演变换,L变成了过反演中心的圆(O5),O3,O4分别变成了原来的圆O1,O2,由相切...
  • Mindis Time Limit: 6000/3000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others) Special Judge Problem Description The center coordinate of the circle C is O, the coordinate of O is
  • 前言:让大家对网站架构的发展有一个模板式的展现,并且要保持好的架构的价值观,架构的发展演变和业务的驱动其实是互相影响的结果,业务驱动着架构的演变,而架构的健壮又会作用于业务的蓬勃开展。不能一味地要...
  • 数学反演思想及其发展,刘建忠,刘心蓉,讨论了反演变换、级数反演、反演理论、关系映射反演方法和反演集合理论的思想差异和相互之间关系,指出:关系映射反演方法思想包
  • 虽然没有“关于圆对称”的正式说法,但是的确有一种变换能够产生类似的效果——反演变换。它不仅是平面几何中的一个强力工具,还在复分析和双曲几何等领域占据一定地位。这篇文章就来说说平面几何中的反演变换。注:...
  • CAGD课件,包括 空间角度 插值曲线曲面 亲似变换 仿射变换 Bezier曲线曲面 spline曲线曲面 反演变换 拓扑变换 有理曲线曲面 函数曲线曲面 三角剖分
  • 反演变换:转换成直线经过多少个圆 #include #include #include #include using namespace std; #define eps 1e-8 const double pi=acos(-1.0); int sig(double x){return (x>eps)-(x);} struct P
  • 状态压缩枚举B.Stealing Harry Potter's Precious bfs + dfsC.Zhuge Liang's Password 水题D.Problem of Apollonius 1)方程求解(数学能力) 2)迭代法或者模拟退火 3)反演变换法E.Random Number Gene...
  • 7.4 等角线及其他与位似旋转变换 7.5 三角形的连接与位似旋转变换之积 7.6 位似轴反射变换与几何证题 习题7第8章 反演变换 8.1 反演变换及其性质 8.2 线段度量关系与反演变换 8.3 圆与反演变换 8.4 两圆的互...
  • 题目链接点这里 圆的反演主要有3条性质 ...反演变换不改变图形的相切性. 然后这道题就解决了。。 //注意精度,直接用rad计算圆弧中点, #include #include #include #include #include #include #
  • 首先来看反演变换,首先是给定一个圆圆心为O,半径为R 1、圆外一点P与圆内一点P‘会一一对应的反演OP*OP'=R*R 2、经过O的圆,反演后成为不经过O的一条直线 3、不经过O的圆,反演后成为另一个圆,且圆心并不...
  • Codeforces 372

    2014-01-06 11:06:00
    A  (被装的袋鼠不可以装的袋鼠)贪心,排序,从n/2分成两部分。 B   好一道前缀和的题目。 C  标准算法不难想,m^2的算法见... 反演变换。 转载于:https://www.cnblogs.com/hsuppr/p/3...
  • 如果把以那个定点为原点进行反演变换,那么过定点的圆就变成了直线,不过定点的圆还是圆,问题就转化成了求那两个圆的公切线。求出所有公切线再反演回圆再判是否都是外切。#include using namespace std; #define ...
  • 【圆的反演变换】hdu4773

    千次阅读 2014-03-09 21:46:21
    给定不相交的两个圆以及圆外一点,找一个...首先来看反演变换,首先是给定一个圆圆心为O,半径为R 1、圆外一点P与圆内一点P‘会一一对应的反演OP*OP'=R*R 2、经过O的圆,反演后成为不经过O的一条直线 3、不经过O的
  • “请您坐到设计师工位上来。” 1 企业或产品的LOGO,是一种独有且特异的标志,能够最直观且最形象地体现企业及产品的功能与风貌。如果企业及产品的功能有所变化或升级,...IE浏览器LOGO的演变 2015年,微软推出了...
  • 1.数字演变的过程要想理解短视频究竟是风口还是趋势,一定要去过来去看整个互联网数字内容的演变过程。回到若干年前,刚有互联网的时候,在网上传递数据时访问的是二进制的内容,经过解码以后出现了文...
  • 我们从一开始就针对复杂的标量摄动的渐近的德西(AdS)黑洞开始,并解决了整体中重力系统的动力学问题。 当黑洞温度T小于临界值T c时,标量摄动呈指数增长直至饱和,时空的最终状态接近毛状黑洞。 在整体理论中,...
  • 混沌控制模型Lü系统连接了著名的Lorenz系统和Chen系统,并代表了它们之间的连续演变。针对混沌系统的控制问题,已有很多控制方法。本文是针对Lü系统参数未知情形,研究了混沌控制在Lü系统中的问题,并将Lü系统转换...
  • Motorola vs Nokia

    2011-04-02 21:22:00
    在手机市场眼花撩演变中,我们又看到了历史上惊人相似的规律,当一个企业在市场上处于优势地位的时候,都会裹足不前,拒绝新技术,拒绝变化。其实,它就是不想放弃自己目前的优势地位,害怕在新技术面前自己的...
  • 3%的人的偏好,就可以演变成整个社会的意志 第一,少数人极其较真;第二,其他人无所谓;第三点,就是这些人平均分布在社会的各个阶层和各个地区。过来想,如果是边远山区的老爷爷有一个什么嗜好,那他影响不了太...
  • 结合WPF、Silverlight绑定机制,MVP演变出了MVVM,充分利用了WPF、Silverlight的优势,将大量代码逻辑、状态转到ViewModel, 可以说MVVM是专门为WPF、Silverlight打造的。 View绑定到ViewModel,然后执行一些命令在...
  • 1.1 C语言的演变 2 1.1.1 传统C 2 1.1.2 标准C(1989) 2 1.1.3 标准C(1995) 3 1.1.4 标准C(1999) 3 1.1.5 标准C++ 4 1.1.6 本书内容 4 1.2 应该使用哪种C语言 4 1.3 C编程概述 5 1.4 一致性 6 1.5 ...
  • 12.6.2.1 身性 298 12.6.3 类型转换例子 299 12.6.4 自动类型转换的缺陷 300 12.6.4.1 隐藏的行为 301 12.7 小结 302 12.8 练习 302 第13章 动态对象创建 305 13.1 对象创建 305 13.1.1 c从堆中获取存储...
  • 内容简介 《Oracle PL/SQL程序设计(第5版)(套装上下册)》基于Oracle数据库11g,从PL/SQL编程、PL/SQL程序结构、PL/SQL程序数据、PL/SQL中的SQL、PL/SQL应用构建、高级PL/SQL主题这6个方面详细系统地讨论了PL/SQL...

空空如也

空空如也

1 2
收藏数 36
精华内容 14
关键字:

反演变换