/ SeriousOJ /

Record Detail

Accepted


  
# Status Time Cost Memory Cost
#1 Accepted 1ms 584.0 KiB
#2 Accepted 1ms 540.0 KiB
#3 Accepted 2ms 540.0 KiB
#4 Accepted 1ms 540.0 KiB
#5 Accepted 1ms 540.0 KiB
#6 Accepted 2ms 540.0 KiB
#7 Accepted 1ms 540.0 KiB
#8 Accepted 1ms 332.0 KiB
#9 Accepted 1ms 560.0 KiB
#10 Accepted 1ms 540.0 KiB
#11 Accepted 1ms 332.0 KiB
#12 Accepted 1ms 776.0 KiB
#13 Accepted 1ms 560.0 KiB
#14 Accepted 1ms 540.0 KiB
#15 Accepted 1ms 328.0 KiB
#16 Accepted 2ms 328.0 KiB
#17 Accepted 1ms 540.0 KiB
#18 Accepted 1ms 772.0 KiB
#19 Accepted 1ms 332.0 KiB
#20 Accepted 1ms 588.0 KiB

Code

#include <bits/stdc++.h>
using namespace std;

struct Point {
    double x, y;
};

double distance(Point a, Point b) {
    return sqrt((a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y));
}

Point midPoint(Point a, Point b) {
    return {(a.x + b.x) / 2, (a.y + b.y) / 2};
}

pair<Point, double> smallestEnclosingCircle(vector<Point>& points) {
    int n = points.size();
    Point center = points[0];
    double radius = 0.0;

    for (int i = 0; i < n; ++i) {
        if (distance(center, points[i]) > radius) {
            center = points[i];
            radius = 0.0;

            for (int j = 0; j < i; ++j) {
                if (distance(center, points[j]) > radius) {
                    center = midPoint(points[i], points[j]);
                    radius = distance(center, points[j]);

                    for (int k = 0; k < j; ++k) {
                        if (distance(center, points[k]) > radius) {
                            double dx1 = points[j].x - points[i].x;
                            double dy1 = points[j].y - points[i].y;
                            double dx2 = points[k].x - points[i].x;
                            double dy2 = points[k].y - points[i].y;

                            double cross = dx1 * dy2 - dy1 * dx2;
                            double c1 = (dx1 * (points[i].x + points[j].x) + dy1 * (points[i].y + points[j].y)) / 2;
                            double c2 = (dx2 * (points[i].x + points[k].x) + dy2 * (points[i].y + points[k].y)) / 2;

                            center.x = (dy2 * c1 - dy1 * c2) / cross;
                            center.y = (dx1 * c2 - dx2 * c1) / cross;
                            radius = distance(center, points[k]);
                        }
                    }
                }
            }
        }
    }

    return {center, radius};
}

int main() {
    int n;
    cin >> n;

    vector<Point> points(n);
    for (int i = 0; i < n; ++i) {
        cin >> points[i].x >> points[i].y;
    }

    pair<Point, double> result = smallestEnclosingCircle(points);

    cout << fixed << setprecision(15) << result.second << endl;
    return 0;
}

Information

Submit By
Type
Submission
Problem
P1123 Relic Rescue Radius!
Language
C++17 (G++ 13.2.0)
Submit At
2024-12-13 17:41:11
Judged At
2024-12-13 17:41:11
Judged By
Score
100
Total Time
2ms
Peak Memory
776.0 KiB