【UVA12304】2D Geometry 110 in 1!（外接圆/内切圆/切点等圆相关问题的模版题）
题目地址：https://vjudge.net/problem/UVA-12304
题目：
看这里：https://uva.onlinejudge.org/external/123/12304.pdf
解题思路：
紫书P267-P269将的很清楚了，新的知识点是直线平移的求法：
直线
1.求出单位法向量normal
Point Verunit(Point a) //单位法向量
{
return Point(-a.y, a.x) / Length(a);
}
Point normal = Verunit(v); 2.借助单位法向量和平移距离d求出直线
new_line = Line(p+normal*d, v) 其中p+noraml*d是p在平移后的直线对应的坐标p’
ac代码：
代码有点长，验板子题
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 10;
const double eps = 1e-6;//eps用于控制精度,或者更高精度
const double pi = acos(-1.0);//pi
// 点
struct Point//点或向量
{
double x, y;
Point(double x = 0, double y = 0) :x(x), y(y) {}
friend bool operator < (Point a, Point b)
{
return a.x == b.x ? a.y < b.y : a.x < b.x;
}
};
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)//精度三态函数(>0,<0,=0)
{
if (fabs(x) < eps)return 0; //等于
else return x < 0 ? -1 : 1;//小于，大于
}
bool operator == (const Point &a, const Point &b)//向量相等
{
return dcmp(a.x - b.x) == 0 && dcmp(a.y - b.y) == 0;
}
//点的辅助函数
double Dot(Vector a, Vector b)//点积
{
return a.x * b.x + a.y * b.y;
}
double Cross(Vector a, Vector b)//外积
{
return a.x * b.y - a.y * b.x;
}
double Length(Vector a)//模
{
return sqrt(Dot(a, a));
}
Vector Rotate(Vector a, double rad)//逆时针旋转rad弧度
{
return Vector(a.x*cos(rad) - a.y*sin(rad), a.x*sin(rad) + a.y*cos(rad));
}
double Angle(Point a)//极角
{
return atan2(a.y, a.x);
}
double RadToDegree(double rad)//弧度转角度
{
return 180.0*rad/pi;
}
Point Verunit(Point a) //单位法向量
{
return Point(-a.y, a.x) / Length(a);
}
double DistanceToLine(Point P, Point A, Point B)//点P到AB所在直线的距离
{
Vector v1 = B - A, v2 = P - A;
return fabs(Cross(v1, v2)) / Length(v1);
}
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{ // p+v*t t是变量
Point p;
Point v;//方向向量
double ang;//斜率
Line(Point _p, Point _v):p(_p),v(_v){ang = atan2(v.y, v.x);}
Point point(double a) // 直线上某一点
{
return p+v*a;
}
friend bool operator < (Line a, Line b)
{
return a.ang < b.ang;
}
};
//两圆交点
int getCirleCirleIntersection(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;//重合
else 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;
}
// 直线交点，P，方向向量v
Point GetLineIntersection(Point P, Vector v, Point Q, Vector w)
{
Vector u = P - Q;//QP
double t = Cross(w, u) / Cross(v, w);
return P + v * t;
}
//直线和圆的交点
int getLineCircleIntersection(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); sol.push_back(L.point(t1));
t2 = (-f + sqrt(delta)) / (2*e); sol.push_back(L.point(t2));
return 2;
}
//外接圆
Circle CircumscribedCircle(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(p1-p));
}
//内切圆
Circle InscribedCircle(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, DistanceToLine(p, p1, p2));
}
//过定点做圆的切线, 返回切点个数,v中存切点
int TangentLineThroughPoint(Point p, Circle C, Vector* v)
{
Vector u = C.c - p;
double dist = Length(u);
if(dist < C.r) return 0;//inside
else if(dcmp(dist - C.r) == 0)//on the circle
{
v[0] = Rotate(u, pi/2);
return 1;
}
else //outside
{
double ang = asin(C.r / dist);
v[0] = Rotate(u, -ang);
v[1] = Rotate(u, ang);
return 2;
}
}
int main()
{
//freopen("/Users/zhangkanqi/Desktop/11.txt","r",stdin);
char op[200];
double a[20];
Point v[10];//存直线和圆的切点
double degree[10];//存极角
vector<Point> sol;//存坐标
while(~scanf("%s", op))
{
if(strcmp(op, "CircumscribedCircle") == 0)
{
for(int i = 1; i <= 6; i++) scanf("%lf", &a[i]);
Circle C = CircumscribedCircle(Point(a[1], a[2]), Point(a[3], a[4]), Point(a[5], a[6]));
printf("(%.6lf,%.6lf,%.6lf)\n", C.c.x, C.c.y, C.r);
}
else if(strcmp(op, "InscribedCircle") == 0)
{
for(int i = 1; i <= 6; i++) scanf("%lf", &a[i]);
Circle C = InscribedCircle(Point(a[1], a[2]), Point(a[3], a[4]), Point(a[5], a[6]));
printf("(%.6lf,%.6lf,%.6lf)\n", C.c.x, C.c.y, C.r);
}
else if(strcmp(op, "TangentLineThroughPoint") == 0)
{
for(int i = 1; i <= 5; i++) scanf("%lf", &a[i]);
int num = TangentLineThroughPoint(Point(a[4], a[5]), Circle(Point(a[1], a[2]), a[3]), v);
if(!num)
{
printf("[]\n");
continue;
}
for(int i = 0; i < num; i++)
{
double de = RadToDegree(Angle(v[i]));//极角可能是负的，不符合条件的情况：de<0,de>=180
if(dcmp(de) < 0) de = 180.0 + de; // de < 0
else while(dcmp(de-180.0) >= 0) de -= 180.0; // de >= 180
degree[i] = de;
}
sort(degree, degree+num);
printf("[");
for(int i = 0; i < num; i++)
{
if(i) printf(",");
printf("%.6lf", degree[i]);
}
printf("]\n");
}
else if(strcmp(op, "CircleThroughAPointAndTangentToALineWithRadius") == 0)
{
for(int i = 1; i <= 7; i++) scanf("%lf", &a[i]);
Point A = Point(a[3], a[4]), B = Point(a[5], a[6]);
Circle C = Circle(Point(a[1], a[2]), a[7]);
Point normal = Verunit(B-A) * a[7];
//获得和BA这条直线平行且距离为r的直线
Line l1 = Line(A+normal, B-A), l2 = Line(A-normal, B-A);
//转化为两直线和圆的交点
sol.clear();
double t1 = -1,t2 = -1;//两交点的极角
getLineCircleIntersection(l1,C,t1,t2,sol);
getLineCircleIntersection(l2,C,t1,t2,sol);
sort(sol.begin(), sol.end());
printf("[");
for(int i = 0; i < sol.size(); i++)
{
if(i) printf(",");
printf("(%.6lf,%.6lf)", sol[i].x, sol[i].y);
}
printf("]\n");
}
else if(strcmp(op, "CircleTangentToTwoLinesWithRadius") == 0)
{
for(int i = 1; i <= 9; i++) scanf("%lf", &a[i]);
Point A = Point(a[1],a[2]), B = Point(a[3],a[4]);
Point C = Point(a[5],a[6]), D = Point(a[7], a[8]);
Point normal1 = Verunit(B-A) * a[9];
Point normal2 = Verunit(D-C) * a[9];
//转化为求两两直线交点,已经保证必有交点
sol.clear();
sol.push_back(GetLineIntersection(A+normal1, B-A, C+normal2, D-C));
sol.push_back(GetLineIntersection(A+normal1, B-A, C-normal2, D-C));
sol.push_back(GetLineIntersection(A-normal1, B-A, C+normal2, D-C));
sol.push_back(GetLineIntersection(A-normal1, B-A, C-normal2, D-C));
sort(sol.begin(), sol.end());
printf("[");
for(int i = 0; i < sol.size(); i++)
{
if(i) printf(",");
printf("(%.6lf,%.6lf)",sol[i].x, sol[i].y);
}
printf("]\n");
}
else if(strcmp(op, "CircleTangentToTwoDisjointCirclesWithRadius") == 0)
{
for(int i = 1; i <= 7; i++) scanf("%lf", &a[i]);
Circle c1 = Circle(Point(a[1],a[2]),a[3]+a[7]);
Circle c2 = Circle(Point(a[4],a[5]),a[6]+a[7]);
//转化为两圆交点
sol.clear();
getCirleCirleIntersection(c1, c2, sol);
sort(sol.begin(), sol.end());
printf("[");
for(int i = 0; i < sol.size(); i++)
{
if(i) printf(",");
printf("(%.6lf,%.6lf)",sol[i].x, sol[i].y);
}
printf("]\n");
}
}
return 0;
}
/**
output:
(9.734940,5.801205,11.332389)
(9.113006,6.107686,5.644984)
[53.977231,160.730818]
[0.000000]
[]
[(112.047575,299.271627),(199.997744,199.328253)]
[(-0.071352,123.937211),(150.071352,256.062789)]
[(100.000000,200.000000)]
[]
[(72.231286,121.451368),(87.815122,63.011983),(128.242785,144.270867),(143.826621,85.831483)]
[(157.131525,134.836744),(194.943947,202.899105)]
[(204.000000,178.000000)]
*/
