1 条题解

  • 0
    @ 2025-5-5 12:04:37
    #include <iostream>
    #include <cmath>
    #include <vector>
    #include <cstdlib>
    using namespace std;
    
    struct Point {
        char label;
        int x, y;
    };
    
    double area(const Point& a, const Point& b, const Point& c) {
        return fabs((double)(b.x - a.x) * (c.y - a.y) - (b.y - a.y) * (c.x - a.x)) / 2.0;
    }
    
    bool is_inside(const Point& p, const Point& a, const Point& b, const Point& c) {
        double A = area(a, b, c);
        double A1 = area(p, b, c);
        double A2 = area(a, p, c);
        double A3 = area(a, b, p);
        return fabs((A1 + A2 + A3) - A) < 1e-6;
    }
    
    bool contains_other(const Point& a, const Point& b, const Point& c, const vector<Point>& points) {
        for (int i = 0; i < points.size(); ++i) {
            Point p = points[i];
            if (p.label == a.label || p.label == b.label || p.label == c.label) continue;
            if (is_inside(p, a, b, c)) return true;
        }
        return false;
    }
    
    int main() {
        int n;
        while (cin >> n && n != 0) {
            vector<Point> points(n);
            for (int i = 0; i < n; ++i) {
                cin >> points[i].label >> points[i].x >> points[i].y;
            }
    
            double max_area = -1;
            string best_triangle = "";
    
            for (int i = 0; i < n; ++i)
                for (int j = i + 1; j < n; ++j)
                    for (int k = j + 1; k < n; ++k) {
                        Point a = points[i], b = points[j], c = points[k];
                        if (contains_other(a, b, c, points)) continue;
                        double ar = area(a, b, c);
                        if (ar > max_area) {
                            max_area = ar;
                            char labels[3] = { a.label, b.label, c.label };
                            for (int x = 0; x < 2; ++x)
                                for (int y = x + 1; y < 3; ++y)
                                    if (labels[x] > labels[y]) {
                                        char temp = labels[x];
                                        labels[x] = labels[y];
                                        labels[y] = temp;
                                    }
                            best_triangle = string() + labels[0] + labels[1] + labels[2];
                        }
                    }
    
            cout << best_triangle << endl;
        }
        return 0;
    }
    
    
    • 1

    信息

    ID
    570
    时间
    1000ms
    内存
    10MiB
    难度
    7
    标签
    递交数
    2
    已通过
    1
    上传者