可真是道恶心题……
首先翻译一下6个任务：
- 给出一个三角形，求它的外界圆。
- 给出一个三角形，求它的内接圆。
- 给出一个圆和一个点，求过这个点的切线的倾斜角\(\alpha \in [0,180)\)。（这个点可能在圆内或圆上）
- 给出一条切线、圆上一点和圆的半径，求圆心位置。（此问题和后面的问题都可能无解或有多个解）
- 给出两条切线和圆的半径，求圆心位置。
- 给出两个外切圆和半径，求圆心位置。
若有多个解，从小到大输出答案。（点排序时以\(x\)为第一关键字）
可以发现，上面的问题经过简单的转换后，就是要求我们实现：
- 求点到直线的距离。
- 求点在直线上的垂足。
- 求直线的垂直平分线。
- 求角的平分线。
- 求两条直线的交点。
- 求圆和一条直线的交点。
- 求两个圆的交点。
然后，我们写\(O(1)\)个小时就能写出来了（大雾
#include <bits/stdc++.h>
using namespace std;
typedef double db;
const db eps = 1e-8, INF = 1.0 / 0.0, pi = acos(-1);
inline int judge(db x) {
return x > -eps ? x > eps ? 1 : 0 : -1;
}
#define NULLP point(INF,INF)
struct point {
db x,y;
point(db x_=0,db y_=0): x(x_), y(y_) {}
db abs() const {
return sqrt(x * x + y * y);
}
db norm() const {
return x * x + y * y;
}
bool operator < (const point& a) const {
return judge(x - a.x) != 0 ? judge(x - a.x) < 0 : judge(y - a.y) < 0;
}
point operator - () const {
return point(-x, -y);
}
point operator * (const db& a) const {
return point(x * a, y * a);
}
point operator / (const db& a) const {
return point(x / a, y / a);
}
point* operator *= (const db& a) {
return *this = *this * a, this;
}
point* operator /= (const db& a) {
return *this = *this / a, this;
}
point operator + (const point& a) const {
return point(x + a.x, y + a.y);
}
point operator - (const point& a) const {
return point(x - a.x, y - a.y);
}
point* operator += (const point& a) {
return *this = *this + a, this;
}
point* operator -= (const point& a) {
return *this = *this - a, this;
}
bool avail() {
return (fabs(x) != INF) && (fabs(y) != INF);
}
};
db dot(point a,point b) {
return a.x * b.x + a.y * b.y;
}
db cross(point a,point b) {
return a.x * b.y - a.y * b.x;
}
point unit(point a) {
db t = a.abs();
if (judge(t) == 0) return a;
return a / t;
}
struct line {
point u,v;
line(point u_=point(),point v_=point()): u(u_) {
v = unit(v_);
}
};
db dist(point u,line l) {
return fabs(cross(u - l.u,l.v));
}
point foot_point(point u,line l) {
return l.u + (l.v * dot(u - l.u,l.v));
}
point perpen(point a) {
return point(a.y, -a.x);
}
point crossover(line a,line b) {
if (judge(cross(a.v,b.v)) == 0) return NULLP;
point f1 = foot_point(b.u,a);
point f2 = foot_point(f1,b);
if (judge(dot(f2 - b.u,b.v)) < 0) b.v = -b.v;
return b.u + b.v * ((f1 - b.u).norm() / (f2 - b.u).abs());
}
line perpen_bi(point a,point b) {
return line((a + b) / 2, perpen(b - a));
}
struct angle {
point o,u,v;
angle(point o_=point(),point u_=point(),point v_=point()): o(o_) {
u = unit(u_);
v = unit(v_);
}
line bise() const {
return line(o,u + v);
}
};
struct circle {
point o;
db r;
circle(point o_=point(),db r_=0): o(o_), r(r_) {}
};
pair<point,point> crossover(circle c,line l) {
point f = foot_point(c.o,l);
db d = dist(c.o,l);
if (judge(d - c.r) > 0) return make_pair(NULLP,NULLP);
if (judge(d - c.r) == 0) return make_pair(f,NULLP);
db t = sqrt(c.r * c.r - d * d);
return make_pair(f + (l.v * t), f - (l.v * t));
}
pair<point,point> crossover(circle c1,circle c2) {
if (judge(c1.r - c2.r) < 0) swap(c1,c2);
db d = (c1.o - c2.o).abs();
if (judge(d - c1.r - c2.r) > 0) return make_pair(NULLP,NULLP);
if (judge(c1.r - c2.r - d) > 0) return make_pair(NULLP,NULLP);
db co = (d * d + c1.r * c1.r - c2.r * c2.r) / (2 * d * c1.r);
line l = line(c1.o,c2.o - c1.o);
point h = l.u + (l.v * c1.r * co);
line t = line(h,perpen(l.v));
return crossover(c1,t);
}
circle CircumscribedCircle(point a,point b,point c) {
line l1 = perpen_bi(a,b);
line l2 = perpen_bi(b,c);
point o = crossover(l1,l2);
return circle(o,(o - a).abs());
}
circle InscribedCircle(point a,point b,point c) {
angle a1 = angle(a,b - a,c - a);
angle a2 = angle(b,a - b,c - b);
line l1 = a1.bise();
line l2 = a2.bise();
point o = crossover(l1,l2);
return circle(o,dist(o,line(a,b-a)));
}
void TangentLineThroughPoint(circle c,point p) {
db d = (p - c.o).abs();
if (judge(d - c.r) < 0) return (void) (puts("[]"));
if (judge(d - c.r) == 0) {
point t = perpen(p - c.o);
db ret = atan(t.y / t.x) / pi * 180;
if (judge(ret) < 0) ret = ret + 180;
return (void) (printf("[%.6lf]\n",ret));
}
db r = sqrt(d * d - c.r * c.r);
pair<point,point> tmp = crossover(circle(p,r),c);
point t;
db ret1, ret2;
t = tmp.first - p;
ret1 = atan(t.y / t.x) / pi * 180;
if (judge(ret1) < 0) ret1 += 180;
t = tmp.second - p;
ret2 = atan(t.y / t.x) / pi * 180;
if (judge(ret2) < 0) ret2 += 180;
if (judge(ret1 - ret2) > 0) swap(ret1,ret2);
printf("[%.6lf,%.6lf]\n",ret1,ret2);
}
void output(vector<point>& ret) {
sort(ret.begin(),ret.end());
if (ret.size() == 0) return (void) (puts("[]"));
printf("[(%.6lf,%.6lf)",ret[0].x,ret[0].y);
for (int i = 1 ; i < (int)ret.size() ; ++ i)
printf(",(%.6lf,%.6lf)",ret[i].x,ret[i].y);
puts("]");
}
void CircleThroughAPointAndTangentToALineWithRadius(point p,line l,db r) {
static vector<point> ret;
ret.clear();
point t = perpen(l.v);
line l1 = line(l.u + (t * r),l.v);
line l2 = line(l.u - (t * r),l.v);
circle c = circle(p,r);
pair<point,point> tmp;
tmp = crossover(c,l1);
if (tmp.first.avail()) ret.push_back(tmp.first);
if (tmp.second.avail()) ret.push_back(tmp.second);
tmp = crossover(c,l2);
if (tmp.first.avail()) ret.push_back(tmp.first);
if (tmp.second.avail()) ret.push_back(tmp.second);
output(ret);
}
void CircleTangentToTwoLinesWithRadius(line a,line b,db r) {
static vector<point> ret;
ret.clear();
point t;
t = perpen(a.v);
line a1 = line(a.u + (t * r),a.v);
line a2 = line(a.u - (t * r),a.v);
t = perpen(b.v);
line b1 = line(b.u + (t * r),b.v);
line b2 = line(b.u - (t * r),b.v);
t = crossover(a1,b1);
if (t.avail()) ret.push_back(t);
t = crossover(a1,b2);
if (t.avail()) ret.push_back(t);
t = crossover(a2,b1);
if (t.avail()) ret.push_back(t);
t = crossover(a2,b2);
if (t.avail()) ret.push_back(t);
output(ret);
}
void CircleTangentToTwoDisjointCirclesWithRadius(circle c1,circle c2,db r) {
static vector<point> ret;
ret.clear();
c1.r += r;
c2.r += r;
pair<point,point> tmp;
tmp = crossover(c1,c2);
if (tmp.first.avail()) ret.push_back(tmp.first);
if (tmp.second.avail()) ret.push_back(tmp.second);
output(ret);
}
int main() {
string tmp;
point a,b,c,d;
circle cir;
db t,t1,t2;
while (cin >> tmp) {
if (tmp == "CircumscribedCircle") {
scanf("%lf%lf%lf%lf%lf%lf",&a.x,&a.y,&b.x,&b.y,&c.x,&c.y);
cir = CircumscribedCircle(a,b,c);
printf("(%.6lf,%.6lf,%.6lf)\n",cir.o.x,cir.o.y,cir.r);
}
if (tmp == "InscribedCircle") {
scanf("%lf%lf%lf%lf%lf%lf",&a.x,&a.y,&b.x,&b.y,&c.x,&c.y);
cir = InscribedCircle(a,b,c);
printf("(%.6lf,%.6lf,%.6lf)\n",cir.o.x,cir.o.y,cir.r);
}
if (tmp == "TangentLineThroughPoint") {
scanf("%lf%lf%lf%lf%lf",&cir.o.x,&cir.o.y,&cir.r,&a.x,&a.y);
TangentLineThroughPoint(cir,a);
}
if (tmp == "CircleThroughAPointAndTangentToALineWithRadius") {
scanf("%lf%lf%lf%lf%lf%lf%lf",&a.x,&a.y,&b.x,&b.y,&c.x,&c.y,&t);
CircleThroughAPointAndTangentToALineWithRadius(a,line(b,c - b),t);
}
if (tmp == "CircleTangentToTwoLinesWithRadius") {
scanf("%lf%lf%lf%lf%lf%lf%lf%lf%lf",&a.x,&a.y,&b.x,&b.y,&c.x,&c.y,&d.x,&d.y,&t);
CircleTangentToTwoLinesWithRadius(line(a,b-a),line(c,d-c),t);
}
if (tmp == "CircleTangentToTwoDisjointCirclesWithRadius") {
scanf("%lf%lf%lf%lf%lf%lf%lf",&a.x,&a.y,&t1,&b.x,&b.y,&t2,&t);
CircleTangentToTwoDisjointCirclesWithRadius(circle(a,t1),circle(b,t2),t);
}
}
return 0;
}
小结：我写得太久了。敲键盘时还总是有迟疑。