列表

详情

NC243843. 2D Geometry 110 in 1!

描述

This is a collection of 110 (in binary) 2D geometry problems.
CircumscribedCircle x1 y1 x2 y2 x3 y3
Find out the circumscribed circle of triangle (x1,y1)-(x2,y2)-(x3,y3). These three points are guaranteed to be non-collinear. The circle is formatted as (x,y,r) where (x,y) is the center of circle, r is the radius.

InscribedCircle x1 y1 x2 y2 x3 y3
Find out the inscribed circle of triangle (x1,y1)-(x2,y2)-(x3,y3). These three points are guaranteed to be non-collinear. The circle is formatted as (x,y,r) where (x,y) is the center of circle, r is the radius.

TangentLineThroughPoint xc yc r xp yp
Find out the list of tangent lines of circle centered (xc,yc) with radius r that pass through point (xp,yp). Each tangent line is formatted as a single real number “angle” (in degrees), the angle of the line (0<=angle<180). Note that the answer should be formatted as a list (see below for details). If there is no answer, you should print an empty list.



CircleThroughAPointAndTangentToALineWithRadius xp yp x1 y1 x2 y2 r
Find out the list of circles passing through point (xp, yp) that is tangent to a line (x1,y1)-(x2,y2) with radius r. Each circle is formatted as (x,y), since the radius is already given. Note that the answer should be formatted as a list. If there is no answer, you should print an empty list.


CircleTangentToTwoLinesWithRadius x1 y1 x2 y2 x3 y3 x4 y4 r
Find out the list of circles tangent to two non-parallel lines (x1,y1)-(x2,y2) and (x3,y3)-(x4,y4), having radius r. Each circle is formatted as (x,y), since the radius is already given. Note that the answer should be formatted as a list. If there is no answer, you should print an empty list.


CircleTangentToTwoDisjointCirclesWithRadius x1 y1 r1 x2 y2 r2 r
Find out the list of circles externally tangent to two disjoint circles (x1,y1,r1) and (x2,y2,r2), having radius r. By “externally” we mean it should not enclose the two given circles. Each circle is formatted as (x,y), since the radius is already given. Note that the answer should be formatted as a list. If there is no answer, you should print an empty list.


For each line described above, the two endpoints will not be equal. When formatting a list of real numbers, the numbers should be sorted in increasing order; when formatting a list of (x,y) pairs, the pairs should be sorted in increasing order of x. In case of tie, smaller y comes first.

输入描述

There will be at most 1000 sub-problems, one in each line, formatted as above. The coordinates will be integers with absolute value not greater than 1000. The input is terminated by end of file (EOF).

输出描述

For each input line, print out your answer formatted as stated in the problem description. Each number in the output should be rounded to four digits after the decimal point. Note that the list should be enclosed by square brackets, and tuples should be enclosed by brackets. There should be no space characters in each line of your output.

示例1

输入: 

CircumscribedCircle 0 0 20 1 8 17
InscribedCircle 0 0 20 1 8 17
TangentLineThroughPoint 200 200 100 40 150
TangentLineThroughPoint 200 200 100 200 100
TangentLineThroughPoint 200 200 100 270 210
CircleThroughAPointAndTangentToALineWithRadius 100 200 75 190 185 65 100
CircleThroughAPointAndTangentToALineWithRadius 75 190 75 190 185 65 100
CircleThroughAPointAndTangentToALineWithRadius 100 300 100 100 200 100 100
CircleThroughAPointAndTangentToALineWithRadius 100 300 100 100 200 100 99
CircleTangentToTwoLinesWithRadius 50 80 320 190 85 190 125 40 30
CircleTangentToTwoDisjointCirclesWithRadius 120 200 50 210 150 30 25
CircleTangentToTwoDisjointCirclesWithRadius 100 100 80 300 250 70 50

输出: 

(9.7349,5.8012,11.3324)
(9.1130,6.1077,5.6450)
[53.9772,160.7308]
[0.0000]
[]
[(112.0476,299.2716),(199.9977,199.3283)]
[(-0.0714,123.9372),(150.0714,256.0628)]
[(100.0000,200.0000)]
[]
[(72.2313,121.4514),(87.8151,63.0120),(128.2428,144.2709),(143.8266,85.8315)]
[(157.1315,134.8367),(194.9439,202.8991)]
[(204.0000,178.0000)]

原站题解

上次编辑到这里，代码来自缓存 点击恢复默认模板

C++(clang++ 11.0.1) 解法, 执行用时: 10ms, 内存消耗: 496K, 提交时间: 2023-08-06 15:13:22 

#include <bits/stdc++.h>
// #define int long long int
#define all(x) x.begin(), x.end()
#define c1() cout << " ----------------------------- \n";
#define c2() cout << " +++++++++++++++++++++++++++++ \n";
#define cr(x) cout << "[ " << #x << " = " << x << " ]\n";
#define ct(x, y) cout << "[ " << #x << " = " << x << ", " << #y << " = " << y << " ]\n";
#define IOS ios::sync_with_stdio(0), cin.tie(0), cout.tie(0)
using namespace std;

using point_t = long double; // 全局数据类型，可修改为 long long 等

constexpr point_t eps = 1e-8;
constexpr long double PI = 3.1415926535897932384l;

// 点与向量
template <typename T>
struct point
{
    T x, y;

    bool operator==(const point &a) const { return (abs(x - a.x) <= eps && abs(y - a.y) <= eps); }
    bool operator<(const point &a) const
    {
        if (abs(x - a.x) <= eps)
            return y < a.y - eps;
        return x < a.x - eps;
    }
    bool operator>(const point &a) const { return !(*this < a || *this == a); }
    point operator+(const point &a) const { return {x + a.x, y + a.y}; }
    point operator-(const point &a) const { return {x - a.x, y - a.y}; }
    point operator-() const { return {-x, -y}; }
    point operator*(const T k) const { return {k * x, k * y}; }
    point operator/(const T k) const { return {x / k, y / k}; }
    T operator*(const point &a) const { return x * a.x + y * a.y; } // 点积
    T operator^(const point &a) const { return x * a.y - y * a.x; } // 叉积，注意优先级
    int toleft(const point &a) const
    {
        const auto t = (*this) ^ a;
        return (t > eps) - (t < -eps);
    }                                                             // to-left 测试
    T len2() const { return (*this) * (*this); }                  // 向量长度的平方
    T dis2(const point &a) const { return (a - (*this)).len2(); } // 两点距离的平方

    // 涉及浮点数
    long double len() const { return sqrtl(len2()); }                                                                      // 向量长度
    long double dis(const point &a) const { return sqrtl(dis2(a)); }                                                       // 两点距离
    long double ang(const point &a) const { return acosl(max(-1.0l, min(1.0l, ((*this) * a) / (len() * a.len())))); }      // 向量夹角
    point rot(const long double rad) const { return {x * cos(rad) - y * sin(rad), x * sin(rad) + y * cos(rad)}; }          // 逆时针旋转（给定角度）
    point rot(const long double cosr, const long double sinr) const { return {x * cosr - y * sinr, x * sinr + y * cosr}; } // 逆时针旋转（给定角度的正弦与余弦）
};

using Point = point<point_t>;

// 极角排序
struct argcmp
{
    bool operator()(const Point &a, const Point &b) const
    {
        const auto quad = [](const Point &a)
        {
            if (a.y < -eps)
                return 1;
            if (a.y > eps)
                return 4;
            if (a.x < -eps)
                return 5;
            if (a.x > eps)
                return 3;
            return 2;
        };
        const int qa = quad(a), qb = quad(b);
        if (qa != qb)
            return qa < qb;
        const auto t = a ^ b;
        // if (abs(t)<=eps) return a*a<b*b-eps;  // 不同长度的向量需要分开
        return t > eps;
    }
};

// 直线
template <typename T>
struct line
{
    point<T> p, v; // p 为直线上一点，v 为方向向量

    bool operator==(const line &a) const { return v.toleft(a.v) == 0 && v.toleft(p - a.p) == 0; }
    int toleft(const point<T> &a) const { return v.toleft(a - p); } // to-left 测试
    bool operator<(const line &a) const                             // 半平面交算法定义的排序
    {
        if (abs(v ^ a.v) <= eps && v * a.v >= -eps)
            return toleft(a.p) == -1;
        return argcmp()(v, a.v);
    }

    // 涉及浮点数
    point<T> inter(const line &a) const { return p + v * ((a.v ^ (p - a.p)) / (v ^ a.v)); } // 直线交点
    long double dis(const point<T> &a) const { return abs(v ^ (a - p)) / v.len(); }         // 点到直线距离
    point<T> proj(const point<T> &a) const { return p + v * ((v * (a - p)) / (v * v)); }    // 点在直线上的投影
};

using Line = line<point_t>;

// 线段
template <typename T>
struct segment
{
    point<T> a, b;

    bool operator<(const segment &s) const { return make_pair(a, b) < make_pair(s.a, s.b); }

    // 判定性函数建议在整数域使用

    // 判断点是否在线段上
    // -1 点在线段端点 | 0 点不在线段上 | 1 点严格在线段上
    int is_on(const point<T> &p) const
    {
        if (p == a || p == b)
            return -1;
        return (p - a).toleft(p - b) == 0 && (p - a) * (p - b) < -eps;
    }

    // 判断线段直线是否相交
    // -1 直线经过线段端点 | 0 线段和直线不相交 | 1 线段和直线严格相交
    int is_inter(const line<T> &l) const
    {
        if (l.toleft(a) == 0 || l.toleft(b) == 0)
            return -1;
        return l.toleft(a) != l.toleft(b);
    }

    // 判断两线段是否相交
    // -1 在某一线段端点处相交 | 0 两线段不相交 | 1 两线段严格相交
    int is_inter(const segment<T> &s) const
    {
        if (is_on(s.a) || is_on(s.b) || s.is_on(a) || s.is_on(b))
            return -1;
        const line<T> l{a, b - a}, ls{s.a, s.b - s.a};
        return l.toleft(s.a) * l.toleft(s.b) == -1 && ls.toleft(a) * ls.toleft(b) == -1;
    }

    // 点到线段距离
    long double dis(const point<T> &p) const
    {
        if ((p - a) * (b - a) < -eps || (p - b) * (a - b) < -eps)
            return min(p.dis(a), p.dis(b));
        const line<T> l{a, b - a};
        return l.dis(p);
    }

    // 两线段间距离
    long double dis(const segment<T> &s) const
    {
        if (is_inter(s))
            return 0;
        return min({dis(s.a), dis(s.b), s.dis(a), s.dis(b)});
    }
};

using Segment = segment<point_t>;

// 圆
struct Circle
{
    Point c;
    long double r;

    bool operator==(const Circle &a) const { return c == a.c && abs(r - a.r) <= eps; }
    long double circ() const { return 2 * PI * r; } // 周长
    long double area() const { return PI * r * r; } // 面积

    // 点与圆的关系
    // -1 圆上 | 0 圆外 | 1 圆内
    int is_in(const Point &p) const
    {
        const long double d = p.dis(c);
        return abs(d - r) <= eps ? -1 : d < r - eps;
    }

    // 直线与圆关系
    // 0 相离 | 1 相切 | 2 相交
    int relation(const Line &l) const
    {
        const long double d = l.dis(c);
        if (d > r + eps)
            return 0;
        if (abs(d - r) <= eps)
            return 1;
        return 2;
    }

    // 圆与圆关系
    // -1 相同 | 0 相离 | 1 外切 | 2 相交 | 3 内切 | 4 内含
    int relation(const Circle &a) const
    {
        if (*this == a)
            return -1;
        const long double d = c.dis(a.c);
        if (d > r + a.r + eps)
            return 0;
        if (abs(d - r - a.r) <= eps)
            return 1;
        if (abs(d - abs(r - a.r)) <= eps)
            return 3;
        if (d < abs(r - a.r) - eps)
            return 4;
        return 2;
    }

    // 直线与圆的交点
    vector<Point> inter(const Line &l) const
    {
        const long double d = l.dis(c);
        const Point p = l.proj(c);
        const int t = relation(l);
        if (t == 0)
            return vector<Point>();
        if (t == 1)
            return vector<Point>{p};
        const long double k = sqrt(r * r - d * d);
        return vector<Point>{p - (l.v / l.v.len()) * k, p + (l.v / l.v.len()) * k};
    }

    // 圆与圆交点
    vector<Point> inter(const Circle &a) const
    {
        const long double d = c.dis(a.c);
        const int t = relation(a);
        if (t == -1 || t == 0 || t == 4)
            return vector<Point>();
        Point e = a.c - c;
        e = e / e.len() * r;
        if (t == 1 || t == 3)
        {
            if (r * r + d * d - a.r * a.r >= -eps)
                return vector<Point>{c + e};
            return vector<Point>{c - e};
        }
        const long double costh = (r * r + d * d - a.r * a.r) / (2 * r * d), sinth = sqrt(1 - costh * costh);
        return vector<Point>{c + e.rot(costh, -sinth), c + e.rot(costh, sinth)};
    }

    // 圆与圆交面积
    long double inter_area(const Circle &a) const
    {
        const long double d = c.dis(a.c);
        const int t = relation(a);
        if (t == -1)
            return area();
        if (t < 2)
            return 0;
        if (t > 2)
            return min(area(), a.area());
        const long double costh1 = (r * r + d * d - a.r * a.r) / (2 * r * d), costh2 = (a.r * a.r + d * d - r * r) / (2 * a.r * d);
        const long double sinth1 = sqrt(1 - costh1 * costh1), sinth2 = sqrt(1 - costh2 * costh2);
        const long double th1 = acos(costh1), th2 = acos(costh2);
        return r * r * (th1 - costh1 * sinth1) + a.r * a.r * (th2 - costh2 * sinth2);
    }

    // 过圆外一点圆的切线
    vector<Line> tangent(const Point &a) const
    {
        const int t = is_in(a);
        if (t == 1)
            return vector<Line>();
        if (t == -1)
        {
            const Point v = {-(a - c).y, (a - c).x};
            return vector<Line>{{a, v}};
        }
        Point e = a - c;
        e = e / e.len() * r;
        const long double costh = r / c.dis(a), sinth = sqrt(1 - costh * costh);
        const Point t1 = c + e.rot(costh, -sinth), t2 = c + e.rot(costh, sinth);
        return vector<Line>{{a, t1 - a}, {a, t2 - a}};
    }

    // 两圆的公切线
    vector<Line> tangent(const Circle &a) const
    {
        const int t = relation(a);
        vector<Line> lines;
        if (t == -1 || t == 4)
            return lines;
        if (t == 1 || t == 3)
        {
            const Point p = inter(a)[0], v = {-(a.c - c).y, (a.c - c).x};
            lines.push_back({p, v});
        }
        const long double d = c.dis(a.c);
        const Point e = (a.c - c) / (a.c - c).len();
        if (t <= 2)
        {
            const long double costh = (r - a.r) / d, sinth = sqrt(1 - costh * costh);
            const Point d1 = e.rot(costh, -sinth), d2 = e.rot(costh, sinth);
            const Point u1 = c + d1 * r, u2 = c + d2 * r, v1 = a.c + d1 * a.r, v2 = a.c + d2 * a.r;
            lines.push_back({u1, v1 - u1});
            lines.push_back({u2, v2 - u2});
        }
        if (t == 0)
        {
            const long double costh = (r + a.r) / d, sinth = sqrt(1 - costh * costh);
            const Point d1 = e.rot(costh, -sinth), d2 = e.rot(costh, sinth);
            const Point u1 = c + d1 * r, u2 = c + d2 * r, v1 = a.c - d1 * a.r, v2 = a.c - d2 * a.r;
            lines.push_back({u1, v1 - u1});
            lines.push_back({u2, v2 - u2});
        }
        return lines;
    }

    // 圆的反演
    tuple<int, Circle, Line> inverse(const Line &l) const
    {
        const Circle null_c = {{0.0, 0.0}, 0.0};
        const Line null_l = {{0.0, 0.0}, {0.0, 0.0}};
        if (l.toleft(c) == 0)
            return {2, null_c, l};
        const Point v = l.toleft(c) == 1 ? Point{l.v.y, -l.v.x} : Point{-l.v.y, l.v.x};
        const long double d = r * r / l.dis(c);
        const Point p = c + v / v.len() * d;
        return {1, {(c + p) / 2, d / 2}, null_l};
    }

    tuple<int, Circle, Line> inverse(const Circle &a) const
    {
        const Circle null_c = {{0.0, 0.0}, 0.0};
        const Line null_l = {{0.0, 0.0}, {0.0, 0.0}};
        const Point v = a.c - c;
        if (a.is_in(c) == -1)
        {
            const long double d = r * r / (a.r + a.r);
            const Point p = c + v / v.len() * d;
            return {2, null_c, {p, {-v.y, v.x}}};
        }
        if (c == a.c)
            return {1, {c, r * r / a.r}, null_l};
        const long double d1 = r * r / (c.dis(a.c) - a.r), d2 = r * r / (c.dis(a.c) + a.r);
        const Point p = c + v / v.len() * d1, q = c + v / v.len() * d2;
        return {1, {(p + q) / 2, p.dis(q) / 2}, null_l};
    }
};

// 三角形 外接圆
Circle CircumscribedCircle(int x1, int y1, int x2, int y2, int x3, int y3)
{
    const Point a = {1.0 * x1, 1.0 * y1}, b = {1.0 * x2, 1.0 * y2}, c = {1.0 * x3, 1.0 * y3};
    const Line l1 = {(a + b) / 2, {-(b - a).y, (b - a).x}}, l2 = {(b + c) / 2, {-(c - b).y, (c - b).x}};
    const Point o = l1.inter(l2);
    return Circle{o, o.dis(a)};
}

// 三角形 内接圆
Circle InscribedCircle(int x1, int y1, int x2, int y2, int x3, int y3)
{
    const Point a = {1.0 * x1, 1.0 * y1}, b = {1.0 * x2, 1.0 * y2}, c = {1.0 * x3, 1.0 * y3};
    const Point ab = (b - a) / (b - a).len(), ac = (c - a) / (c - a).len();
    const Line l1 = {a, (ab + ac) / 2};
    const Point ba = (a - b) / (a - b).len(), bc = (c - b) / (c - b).len();
    const Line l2 = {b, (ba + bc) / 2};
    const Point o = l1.inter(l2);
    return Circle{o, Line{a, b - a}.dis(o)};
}

// 切线通过点
vector<long double> TangentLineThroughPoint(int xc, int yc, int r, int xp, int yp)
{
    const Circle c = {{1.0 * xc, 1.0 * yc}, 1.0 * r};
    const Point p = {1.0 * xp, 1.0 * yp};
    const auto tans = c.tangent(p);
    vector<long double> ans;
    for (const Line &line : tans)
    {
        long double th = atan2(line.v.y, line.v.x);
        if (th < -eps)
            th = PI - abs(th);
        ans.push_back(th / PI * 180);
    }
    sort(ans.begin(), ans.end());
    return ans;
}

// 通过一个点做圆，并与一条有半径的直线相切
vector<Point> CircleThroughAPointAndTangentToALineWithRadius(int xp, int yp, int x1, int y1, int x2, int y2, int r)
{
    const Point p = {1.0 * xp, 1.0 * yp}, a = {1.0 * x1, 1.0 * y1}, b = {1.0 * x2, 1.0 * y2};
    const Circle c = {p, 1.0 * r};
    Point d = {-(b - a).y, (b - a).x};
    d = d / d.len() * r;
    const Line l1 = {a + d, b - a}, l2 = {a - d, b - a};
    const auto t1 = c.inter(l1), t2 = c.inter(l2);
    auto ans = t1;
    ans.insert(ans.end(), t2.begin(), t2.end());
    sort(ans.begin(), ans.end());
    return ans;
}

// 圆与两条具有半径的直线相切
vector<Point> CircleTangentToTwoLinesWithRadius(int x1, int y1, int x2, int y2, int x3, int y3, int x4, int y4, int r)
{
    const Point a = {1.0 * x1, 1.0 * y1}, b = {1.0 * x2, 1.0 * y2}, c = {1.0 * x3, 1.0 * y3}, d = {1.0 * x4, 1.0 * y4};
    Point d1 = {-(b - a).y, (b - a).x};
    d1 = d1 / d1.len() * r;
    Point d2 = {-(d - c).y, (d - c).x};
    d2 = d2 / d2.len() * r;
    const Line l11 = {a + d1, b - a}, l12 = {a - d1, b - a}, l21 = {c + d2, d - c}, l22 = {c - d2, d - c};
    vector<Point> ans = {l11.inter(l21), l11.inter(l22), l12.inter(l21), l12.inter(l22)};
    sort(ans.begin(), ans.end());
    return ans;
}

// 两个半径不相交的圆相切
vector<Point> CircleTangentToTwoDisjointCirclesWithRadius(int x1, int y1, int r1, int x2, int y2, int r2, int r)
{
    const Point a = {1.0 * x1, 1.0 * y1}, b = {1.0 * x2, 1.0 * y2};
    const Circle c = {a, 1.0 * (r1 + r)}, d = {b, 1.0 * (r2 + r)};
    auto ans = c.inter(d);
    sort(ans.begin(), ans.end());
    return ans;
}

int main()
{
    // cout << fixed << setprecision(12);

    string op;
    while (cin >> op)
    {
        if (op == "CircumscribedCircle")
        {
            int x1, y1, x2, y2, x3, y3;
            // cin >> x1 >> y1 >> x2 >> y2 >> x3 >> y3;
            scanf("%d%d%d%d%d%d", &x1, &y1, &x2, &y2, &x3, &y3);
            auto ans = CircumscribedCircle(x1, y1, x2, y2, x3, y3);
            printf("(%.4Lf,%.4Lf,%.4Lf)\n", ans.c.x, ans.c.y, ans.r);
        }
        else if (op == "InscribedCircle")
        {
            int x1, y1, x2, y2, x3, y3;
            scanf("%d%d%d%d%d%d", &x1, &y1, &x2, &y2, &x3, &y3);
            const auto ans = InscribedCircle(x1, y1, x2, y2, x3, y3);
            printf("(%.4Lf,%.4Lf,%.4Lf)\n", ans.c.x, ans.c.y, ans.r);
        }
        else if (op == "TangentLineThroughPoint")
        {
            int xc, yc, r, xp, yp;
            scanf("%d%d%d%d%d", &xc, &yc, &r, &xp, &yp);
            const auto ans = TangentLineThroughPoint(xc, yc, r, xp, yp);
            printf("[");
            for (size_t i = 0; i < ans.size(); i++)
            {
                printf("%.4Lf", ans[i]);
                if (i < ans.size() - 1)
                    printf(",");
            }
            printf("]\n");
        }
        else if (op == "CircleThroughAPointAndTangentToALineWithRadius")
        {
            int xp, yp, x1, y1, x2, y2, r;
            scanf("%d%d%d%d%d%d%d", &xp, &yp, &x1, &y1, &x2, &y2, &r);
            const auto ans = CircleThroughAPointAndTangentToALineWithRadius(xp, yp, x1, y1, x2, y2, r);
            printf("[");
            for (size_t i = 0; i < ans.size(); i++)
            {
                printf("(%.4Lf,%.4Lf)", ans[i].x, ans[i].y);
                if (i < ans.size() - 1)
                    printf(",");
            }
            printf("]\n");
        }
        else if (op == "CircleTangentToTwoLinesWithRadius")
        {
            int x1, y1, x2, y2, x3, y3, x4, y4, r;
            scanf("%d%d%d%d%d%d%d%d%d", &x1, &y1, &x2, &y2, &x3, &y3, &x4, &y4, &r);
            const auto ans = CircleTangentToTwoLinesWithRadius(x1, y1, x2, y2, x3, y3, x4, y4, r);
            printf("[");
            for (size_t i = 0; i < ans.size(); i++)
            {
                printf("(%.4Lf,%.4Lf)", ans[i].x, ans[i].y);
                if (i < ans.size() - 1)
                    printf(",");
            }
            printf("]\n");
        }
        else
        {
            int x1, y1, r1, x2, y2, r2, r;
            scanf("%d%d%d%d%d%d%d", &x1, &y1, &r1, &x2, &y2, &r2, &r);
            const auto ans = CircleTangentToTwoDisjointCirclesWithRadius(x1, y1, r1, x2, y2, r2, r);
            printf("[");
            for (size_t i = 0; i < ans.size(); i++)
            {
                printf("(%.4Lf,%.4Lf)", ans[i].x, ans[i].y);
                if (i < ans.size() - 1)
                    printf(",");
            }
            printf("]\n");
        }
    }

    return 0;
}

上一题

© 2025 nowcoder.com