为什么 long double WA double AC
查看原帖
为什么 long double WA double AC
615348
zesqwq楼主2022/11/23 20:10

double AC 100:\text{double AC 100}:

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

const int N = 1e6 + 10;
struct Point {
    double x, y;
    inline void read() { scanf("%lf %lf", &x, &y); }
} a[N];
inline double sqr(double x) { return x * x; }
inline double dist(Point a, Point b) { return sqr(a.x - b.x) + sqr(a.y - b.y); }
struct Circle {
    double x, y, r;
    inline bool include(Point p) { return dist({x, y}, p) <= r; }
};
int n;
Circle getCircle(Point a, Point b, Point c) {
    double a1 = b.x - a.x, a2 = c.x - a.x, b1 = b.y - a.y, b2 = c.y - a.y;
    double c1 = (sqr(b.x) - sqr(a.x) + sqr(b.y) - sqr(a.y)) / 2, c2 = (sqr(c.x) - sqr(a.x) + sqr(c.y) - sqr(a.y)) / 2;
    Circle ans = {(b2 * c1 - b1 * c2) / (b2 * a1 - b1 * a2), (a2 * c1 - a1 * c2) / (a2 * b1 - a1 * b2), 0.0};
    ans.r = dist({ans.x, ans.y}, a);
    return ans;
}
Circle getMinCircle() {
    Circle ans = {a[1].x, a[1].y, 0.0};
    for (int i = 2; i <= n; i++)
        if (!ans.include(a[i])) {
            ans = {a[i].x, a[i].y, 0};
            for (int j = 1; j < i; j++)
                if (!ans.include(a[j])) {
                    ans = {(a[i].x + a[j].x) / 2, (a[i].y + a[j].y) / 2, dist(a[i], a[j]) / 4};
                    for (int k = 1; k < j; k++)
                        if (!ans.include(a[k])) ans = getCircle(a[i], a[j], a[k]);
                }
        }
    return ans;
}
int main() {
    cin >> n;
    for (int i = 1; i <= n; i++) a[i].read();
    random_shuffle(a + 1, a + n + 1);
    Circle c = getMinCircle();
    printf("%.2lf %.2lf %.2lf", c.x, c.y, sqrt(c.r));
    return 0;
}

long double WA 80:\text{long double WA 80}:

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

const int N = 1e6 + 10;
struct Point {
    long double x, y;
    inline void read() { scanf("%Lf %Lf", &x, &y); }
} a[N];
inline long double sqr(long double x) { return x * x; }
inline long double dist(Point a, Point b) { return sqr(a.x - b.x) + sqr(a.y - b.y); }
struct Circle {
    long double x, y, r;
    inline bool include(Point p) { return dist({x, y}, p) <= r; }
};
int n;
Circle getCircle(Point a, Point b, Point c) {
    long double a1 = b.x - a.x, a2 = c.x - a.x, b1 = b.y - a.y, b2 = c.y - a.y;
    long double c1 = (sqr(b.x) - sqr(a.x) + sqr(b.y) - sqr(a.y)) / 2, c2 = (sqr(c.x) - sqr(a.x) + sqr(c.y) - sqr(a.y)) / 2;
    Circle ans = {(b2 * c1 - b1 * c2) / (b2 * a1 - b1 * a2), (a2 * c1 - a1 * c2) / (a2 * b1 - a1 * b2), 0.0};
    ans.r = dist({ans.x, ans.y}, a);
    return ans;
}
Circle getMinCircle() {
    Circle ans = {a[1].x, a[1].y, 0.0};
    for (int i = 2; i <= n; i++)
        if (!ans.include(a[i])) {
            ans = {a[i].x, a[i].y, 0};
            for (int j = 1; j < i; j++)
                if (!ans.include(a[j])) {
                    ans = {(a[i].x + a[j].x) / 2, (a[i].y + a[j].y) / 2, dist(a[i], a[j]) / 4};
                    for (int k = 1; k < j; k++)
                        if (!ans.include(a[k])) ans = getCircle(a[i], a[j], a[k]);
                }
        }
    return ans;
}
int main() {
    cin >> n;
    for (int i = 1; i <= n; i++) a[i].read();
    random_shuffle(a + 1, a + n + 1);
    Circle c = getMinCircle();
    printf("%.2Lf %.2Lf %.2Lf", c.x, c.y, sqrtf64x(c.r));
    return 0;
}
2022/11/23 20:10
加载中...