二维几何常用模版（圆）

//用到的一些函数和类 看这里

定义圆的类

struct Circle{
  Point c;
  double r;
  Circle(Point c ,double r):c(c),r(r){}
  Point point(double a)
  {
      return Point (c.x+cos(a)*r,c.y+sin(a)*r);
  }
};

定义直线的类

struct Line{
     Vector v;
     Point p;
     Line(Vector V,Point P):v(V),p(P){}
     Point point(double t)
     {
         return p + v*t;
     }
};

求圆与直线的交点

方法一 将直线方程带入圆的方程，求解

int Get_Line_Circle_Intersection(Line L,Circle C,double & t1,double &t2,vector<Point> &sol)
{
    double a = L.v.x,b = L.p.x-C.c.x,c = L.v.y,d = L.p.y - C.c.y;
    double e = a*a + c*c,f = 2*(a*b+c*d),g = b*b+d*d-C.r*C.r;
    double delta = f*f-4*e*g;
    if(dcmp(delta)<0)
        return 0;//相离
    if(dcmp(delta)==0)//相切
    {
        t1 = t2 = -f/(2*e);
        sol.push_back(L.point(t1));
        return 1;
    }
    t1 = (-f+sqrt(delta))/(2*e);
    t2 = (-f-sqrt(delta))/(2*e);
    sol.push_back(L.point(t1));
    sol.push_back(L.point(t2));
    return 2;
}
方法二：几何法

先求圆心在直线的投影点，然后求交线的长度，最后求交点

int Get_Line_Circle_Intersection2(Line L,Circle C,double & t1,double &t2,vector<Point> &sol)
{
    Point p = Get_Line_Projection(C.c,L.p,L.p+L.v);
    double distance = Distance_To_Line(C.c,L.p,L.p+L.v);
    if(dcmp(distance-C.r)>0)
       return 0;
    t1 = t2 =(p.x-L.p.x)/L.v.x;
    if(dcmp(distance-C.r)==0)
    {

        sol.push_back(p);
        return 1;
    }
    distance = sqrt(C.r*C.r-distance*distance);
// cout<<2*distance<<endl;
    distance  = distance/Length(L.v);
    t1 -= distance;
    t2 += distance;
// cout<<distance<<endl;
    sol.push_back(p-L.v*distance);
    sol.push_back(p+L.v*distance);
    return 2;
}

过定点求圆的切线

//过定点求圆的切线
int getTangents(Point p,Circle C,Vector *v)
{
    Vector u = C.c-p;
    double dist = Length(u);
    if(dcmp(dist-C.r)==-1)//没有切线，在圆内
        return 0;
    if(dcmp(dist-C.r)==0)//只有一个切线，点在圆上
    {
        v[0] = Rotate(u,pi/2);
        return 1;
    }
    double ang = asin(C.r/dist);
    v[0] = Rotate(u,-ang);
    v[1] = Rotate(u,+ang);
    return 2;
 }

两圆的公切线

 int getTangents(Circle A,Circle B,Point *a,Point *b)
 {
     int cnt = 0;
     if(A.r < B.r)
     {
         swap(A,B);swap(a,b);
     }
     int d2 = pow(A.c.x-B.c.x,2)+pow(A.c.y-B.c.y,2);
     int rdiff = A.r-B.r;
     int rsum = A.r+B.r;
     if(d2 < rdiff*rdiff)
        return 0;//内含

     double base = atan2(B.c.y-A.c.y,B.c.x-A.c.x);
     if(d2==0&&A.r==B.r)
        return -1;//重合
     if(d2 == rdiff*rdiff)
     {
         a[cnt] = A.point(base);
         b[cnt] = B.point(base);
         cnt++;
         return 1;
     }
     //有外公切线
     double ang = acos((A.r-B.r)/sqrt(d2));
     a[cnt] = A.point(base+ang); b[cnt] = B.point(base+ang); cnt++;
     a[cnt] = A.point(base-ang); b[cnt] = B.point(base-ang); cnt++;
     if(d2==rsum*rsum)
     {
         a[cnt] = A.point(base);b[cnt] = B.point(pi+base);cnt++;
     }
     else if(d2 > rsum*rsum)
     {
         double ang = acos((A.r+B.r)/sqrt(d2));
         a[cnt] = A.point(base+ang);b[cnt] = B.point(base+ang+pi);cnt++;
         a[cnt] = A.point(base-ang);b[cnt] = B.point(base-ang+pi);cnt++;
     }
     return cnt;
 }

模版

#include <cstdio>//C语言io
#include <cstring>//以下是c语言常用头文件
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <cctype>
#include <cstring>
#include <cmath>
#include <iostream>//c++IO
#include <sstream>
#include <string>
#include <list>//c++常用容器
#include <vector>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <algorithm>//c++泛型的一些函数
#include <functional>//用来提供一些模版
#define fo0(i,n) for(int i = 0;i < n; ++i)
#define fo1(i,n) for(int i = 1;i <= n; ++i)
#define mem(ar,num) memset(ar,num,sizeof(ar))
#define me(ar) memset(ar,0,sizeof(ar))
#define lowbit(x) (x&(-x))
using namespace std;
typedef long long LL;
typedef unsigned long long ULL;
const int    prime = 999983;
const int    INF = 0x7FFFFFFF;
const LL     INFF =0x7FFFFFFFFFFFFFFF;
const double pi = acos(-1.0);
const double inf = 1e18;
const double eps = 1e-6;
const LL     mod = 1e9 + 7;
//......................................................

struct Point
{

    double x,y;
    Point(double x = 0,double y = 0):x(x),y(y) {}

};
typedef Point Vector;
Vector operator + (Vector A,Vector B)
{
    return Vector(A.x + B.x,A.y + B.y);
}
Vector operator - (Vector A,Vector B)
{
    return Vector(A.x-B.x,A.y-B.y);
}
Vector operator / (Vector A,double p)
{
    return Vector(A.x/p,A.y/p);
}
Vector operator * (Vector A,double p)
{
    return Vector(A.x*p,A.y*p);
}
int dcmp(double x)
{
    if(fabs(x)<eps)
        return 0;
    else
        return x < 0?-1:1;
}
bool operator < (const Point &a,const Point &b)
{
    if(dcmp(a.x-b.x)==0)
        return a.y<b.y;
    else
        return a.x<b.x;
}

bool operator == (const Point &a,const Point &b)
{
    return !dcmp(a.x-b.x)&&!dcmp(a.y-b.y);
}
double Dot(Vector A,Vector B)
{
    return A.x*B.x+A.y*B.y;
}
double Length(Vector A)
{
    return sqrt(A.x*A.x+A.y*A.y);
}
double Angle(Vector A,Vector B)
{
    return acos(Dot(A,B)/Length(A)/Length(B));
}
double Cross(Vector A,Vector B)
{
    return A.x*B.y - A.y*B.x;
}
double Area2(Point A,Point B,Point C)
{
    return Cross(B-A,C-A);
}
Vector Rotate(Vector A,double rad)
{
    return Vector (A.x*cos(rad)-A.y*sin(rad),A.x*sin(rad)+A.y*cos(rad));
}
Vector Normal(Vector A)//单位法线
{
    double L = Length(A);
    return Vector(-A.y/L,A.x/L);
}
//调用前确保直线有唯一交点，当且仅当Cross(v,w)非0
Point Get_Line_Intersection(Point P,Vector v,Point Q,Vector w)
{
    Vector u = P - Q;
    double t = Cross(w,u)/Cross(v,w);
    return P+v*t;
}
double angle(Vector v)
{
    return atan2(v.y,v.x);
}

double Distance_To_Line(Point P,Point A,Point B)//点到直线的距离
{
    Vector v1 = B-A,v2 = P-A;
    return fabs(Cross(v1,v2)/Length(v1));
}
double Distance_To_Segment(Point P,Point A,Point B)
{
    if(A==B)
        return Length(P-A);
    Vector v1 = B-A,v2 = P-A,v3 = P-B;
    if(dcmp(Dot(v1,v2))<0)
        return Length(v1);
    else if(dcmp(Dot(v1,v3))>0)
        return Length(v3);
    else
        return fabs(Cross(v1,v2))/Length(v1);
}
Point Get_Line_Projection(Point P,Point A,Point B)//求投影点
{
    Vector v = B- A;
    return A + v*(Dot(v,P-A)/Dot(v,v));
}
//线段相交判定 相交不在线段的端点
bool Segment_Proper_Intersection(Point a1,Point a2,Point b1,Point b2)
{
    double c1 =  Cross(a2-a1,b1-a1),c2 = Cross(a2-a1,b2-a1),
           c3 =  Cross(b2-b1,a2-b1),c4 = Cross(b2-b1,a1-b1);
    return dcmp(c1)*dcmp(c2)<0&&dcmp(c3)*dcmp(c4)<0;
}
//判断点是否在线段上(不包括端点）
bool Onsegment(Point p,Point a1,Point a2)
{
    return dcmp(Cross(a1-p,a2-p))==0&&dcmp(Dot(a1-p,a2-p))<0;
}
//多边形的有向面积
//1
double PolygonArea (Point * p,int n)
{
    double area = 0;
    for(int i = 1; i < n - 1; ++i)
    {
        area += Cross(p[i]-p[0],p[i+1]-p[0]);
    }
    return area/2;
}
//2
double PolygonArea2(Point *p,int n)
{
    double area = 0;
    for(int i = 0; i <= n-1; ++i)
    {
        if(i!=n-1)
            area += Cross(p[i],p[i+1]);
        else
            area += Cross(p[n-1],p[0]);
    }
    return area/2;
}
Point Get(Point A,Point B,double rad1,double rad2)
{
    return Get_Line_Intersection(A,Rotate(B-A,rad1/3),B,Rotate(A-B,-rad2/3));
}
struct Circle
{
    Circle() =  default;
    Point c;
    double r;
    Circle(Point c,double r):c(c),r(r) {}
    Point point(double a)
    {
        return Point (c.x+cos(a)*r,c.y+sin(a)*r);
    }
};
struct Line
{
    Line() = default;
    Vector v;
    Point p;
    Line(Vector V,Point P):v(V),p(P) {}
    Point point(double t)
    {
        return p + v*t;
    }
};
int Get_Line_Circle_Intersection(Line L,Circle C,double & t1,double &t2,vector<Point> &sol)
{
    double a = L.v.x,b = L.p.x-C.c.x,c = L.v.y,d = L.p.y - C.c.y;
    double e = a*a + c*c,f = 2*(a*b+c*d),g = b*b+d*d-C.r*C.r;
    double delta = f*f-4*e*g;
    if(dcmp(delta)<0)
        return 0;//相离
    if(dcmp(delta)==0)//相切
    {
        t1 = t2 = -f/(2*e);
        sol.push_back(L.point(t1));
        return 1;
    }
    t1 = (-f+sqrt(delta))/(2*e);
    t2 = (-f-sqrt(delta))/(2*e);
    sol.push_back(L.point(t1));
    sol.push_back(L.point(t2));
    return 2;
}
//几何法
int Get_Line_Circle_Intersection2(Line L,Circle C,double & t1,double &t2,vector<Point> &sol)
{
    Point p = Get_Line_Projection(C.c,L.p,L.p+L.v);
    double distance = Distance_To_Line(C.c,L.p,L.p+L.v);
    if(dcmp(distance-C.r)>0)
        return 0;
    t1 = t2 =(p.x-L.p.x)/L.v.x;
    if(dcmp(distance-C.r)==0)
    {

        sol.push_back(p);
        return 1;
    }
    distance = sqrt(C.r*C.r-distance*distance);
// cout<<2*distance<<endl;
    distance  = distance/Length(L.v);
    t1 -= distance;
    t2 += distance;
// cout<<distance<<endl;
    sol.push_back(p-L.v*distance);
    sol.push_back(p+L.v*distance);
    return 2;
}

//过定点求圆的切线
int getTangents(Point p,Circle C,Vector *v)
{
    Vector u = C.c-p;
    double dist = Length(u);
    if(dcmp(dist-C.r)==-1)
        return 0;
    if(dcmp(dist-C.r)==0)
    {
        v[0] = Rotate(u,pi/2);
        return 1;
    }
    double ang = asin(C.r/dist);
    v[0] = Rotate(u,-ang);
    v[1] = Rotate(u,+ang);
    return 2;
}
//求两圆的公切线
int getTangents(Circle A,Circle B,Point *a,Point *b)
{
    int cnt = 0;
    if(A.r < B.r)
    {
        swap(A,B);
        swap(a,b);
    }
    int d2 = pow(A.c.x-B.c.x,2)+pow(A.c.y-B.c.y,2);
    int rdiff = A.r-B.r;
    int rsum = A.r+B.r;
    if(d2 < rdiff*rdiff)
        return 0;//内含

    double base = atan2(B.c.y-A.c.y,B.c.x-A.c.x);
    if(d2==0&&A.r==B.r)
        return -1;//重合
    if(d2 == rdiff*rdiff)
    {
        a[cnt] = A.point(base);
        b[cnt] = B.point(base);
        cnt++;
        return 1;
    }
    //有外公切线
    double ang = acos((A.r-B.r)/sqrt(d2));
    a[cnt] = A.point(base+ang);
    b[cnt] = B.point(base+ang);
    cnt++;
    a[cnt] = A.point(base-ang);
    b[cnt] = B.point(base-ang);
    cnt++;
    if(d2==rsum*rsum)
    {
        a[cnt] = A.point(base);
        b[cnt] = B.point(pi+base);
        cnt++;
    }
    else if(d2 > rsum*rsum)
    {
        double ang = acos((A.r+B.r)/sqrt(d2));
        a[cnt] = A.point(base+ang);
        b[cnt] = B.point(base+ang+pi);
        cnt++;
        a[cnt] = A.point(base-ang);
        b[cnt] = B.point(base-ang+pi);
        cnt++;
    }
    return cnt;
}
//...........................
//求三角形的外切圆
Circle Circumscribed_Circle(Point A,Point B,Point C)
{
    Vector v1 = Normal(A-B);
    Vector  v2 = Normal(A-C);
    Point c = Get_Line_Intersection((A+B)/2,v1,(A+C)/2,v2);
    return Circle(c,Length(c-A));
}
Circle CircumscribedCircle2(Point p1,Point p2,Point p3)
{
    double Bx=p2.x-p1.x,By=p2.y-p1.y;
    double Cx=p3.x-p1.x,Cy=p3.y-p1.y;

    double D=2*(Bx*Cy-By*Cx);

    double cx=(Cy*(Bx*Bx+By*By)-By*(Cx*Cx+Cy*Cy))/D+p1.x;
    double cy=(Bx*(Cx*Cx+Cy*Cy)-Cx*(Bx*Bx+By*By))/D+p1.y;

    Point p=Point(cx,cy);

    return Circle(p,Length(p-p1));
}
//求三角形的内切圆
int get_Circle_Cricle_Intersection(Circle C1,Circle C2,vector<Point>&sol)
{
    double d =  Length(C1.c-C2.c);
    if(dcmp(d)==0)
    {
        if(dcmp(C1.r-C2.r)==0)
            return -1;
        return 0;
    }
    if(dcmp(C1.r+C2.r-d)<0)
        return 0;
    if(dcmp(fabs(C1.r-C2.r)-d)>0)
        return 0;

    double a = angle(C2.c-C1.c);
    double da = acos((C1.r*C1.r+d*d-C2.r*C2.r)/(2*C1.r*d));
    Point p1 = C1.point(a - da),p2 = C1.point(a+da);
    sol.push_back(p1);
    if(p1 == p2)
        return 1;
    sol.push_back(p2);
    return 2;
}
//Circle Inscribed_Circle(Point p1,Point p2,Point p3)
//{
// double a = Length(p2-p3);
// double b = Length(p3-p1);
// double c = Length(p1-p2);
// Point p = (p1*a+p2*b+p3*c)/(a+b+c);
// return Circle(p,Distance_To_Line(p,p1,p2));
//}
Circle Inscribled_Circle(Point p1,Point p2,Point p3)
{
    double a=Length(p2-p3);
    double b=Length(p3-p1);
    double c=Length(p1-p2);

    Point I=(p1*a+p2*b+p3*c)/(a+b+c);

    return Circle(I,Distance_To_Line(I, p1, p2));

}
Point read_point(void)
{
    Point p;
    scanf("%lf%lf",&p.x,&p.y);
    return p;
}
全部评论

相关推荐

11-25 00:13
广东工业大学 算法工程师
点赞 评论 收藏
分享
不愿透露姓名的神秘牛友
今天 19:05
点赞 评论 收藏
分享
头像
10-23 11:17
百度_智能客服研发组_Java后端开发(实习员工)
阿里系怎么都这个味一个月了也不面？
走下坡路了
牛客263158796号：我领羊一面后十天不挂也不推进 今天问hr说等前序的第一批意向发完看情况再看是否推进
点赞 评论 收藏
分享
10-15 16:27
门头沟学院 C++
感觉被侮辱了
😅
LeoMoon：建议问一下是不是你给他付钱😅😅
点赞 评论 收藏
分享
11-22 18:25
内蒙古财经大学 策略运营
mentor带实习生最烦的是什么？
实习生常见问题及应对建议作为一个过来人，我想和大家分享一下实习生在职场中常见的一些问题，以及如何避免这些问题，让你的实习经历更加顺利。1.&nbsp;好问但不自学很多实习生喜欢问问题，这本身是好事，但有些人不看资料、不做功课就直接来问。比如，明明资料里有答案，却懒得看，直接跑来问：“太复杂了，你跟我说说吧。”&nbsp;还有些基础概念，百度一下就能找到，却还是要问别人。更糟糕的是，问了也记不住，下次还问同样的问题。我的建议是，先自己查资料，实在不懂再问。这样不仅能减轻别人的负担，还能让你学到更多。毕竟，大家都有自己的工作，不可能全天候手把手教你。2.&nbsp;觉得自己被欺负有些实习生觉得被安排整理数据、调研竞品、打印文件...
投递百度等公司10个岗位 >
点赞 评论 收藏
分享
评论
点赞
收藏
分享

全站热榜

正在热议
# 拼多多求职进展汇总 #
232413次浏览 2027人参与
# 在职场上，你最讨厌什么样的同事 #
5660次浏览 81人参与
# 阿里云管培生offer #
58384次浏览 1746人参与
# 25届秋招总结 #
394465次浏览 3951人参与
# 哪些公司校招卡第一学历 #
32683次浏览 104人参与
# 地方国企笔面经互助 #
6486次浏览 16人参与
# 北方华创开奖 #
65840次浏览 547人参与
# ai智能作图 #
20608次浏览 256人参与
# 硬件兄弟们 甩出你的华为奖状 #
77866次浏览 625人参与
# 实习，投递多份简历没人回复怎么办 #
2434878次浏览 34699人参与
# 工作中，你有没有遇到非常爱骂人的领导？ #
4686次浏览 47人参与
# 实习与准备秋招该如何平衡 #
722443次浏览 8551人参与
# 我的实习求职记录 #
6118984次浏览 83941人参与
# 如果再来一次，你还会选择这个工作吗？ #
109625次浏览 1102人参与
# 25届机械人为了秋招做了哪些准备？ #
24917次浏览 355人参与
# 签了三方后想毁约怎么办 #
18518次浏览 111人参与
# 如果你有一天可以担任公司的CEO，你会做哪三件事？ #
9865次浏览 209人参与
# 机械求职避坑tips #
22077次浏览 240人参与
# 游戏求职进展汇总 #
52646次浏览 344人参与
# 夸夸我的求职搭子 #
131958次浏览 1360人参与
# 腾讯求职进展汇总 #
207315次浏览 1694人参与
# 实习想申请秋招offer，能不能argue薪资 #
35738次浏览 308人参与
牛客网
牛客企业服务