QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#261256#7336. FactorygondozuWA 66ms3756kbC++201.9kb2023-11-22 19:33:092023-11-22 19:33:10

Judging History

你现在查看的是最新测评结果

  • [2023-11-22 19:33:10]
  • 评测
  • 测评结果:WA
  • 用时:66ms
  • 内存:3756kb
  • [2023-11-22 19:33:09]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const double MAX = 1e6, EPS = 1e-8;

struct Point{
    double x, y;
};

double getDistance(double x, double y, const vector<Point>& points){
    double dis = 0;
    for(auto p : points){
        dis += sqrt((x-p.x)*(x-p.x) + (y-p.y)*(y-p.y));
    }
    return dis;
}

// returns the minimum distance, and the y coordinate of the optimal point.
pair<double, double> ternarySearchY(double x, const vector<Point>& points){
    double l = -MAX, r = MAX;
    while (r - l > EPS){
        double m1 = l + (r-l)/3;
        double m2 = r - (r-l)/3;

        double dis1 = getDistance(x, m1, points),
               dis2 = getDistance(x, m2, points);

        if(dis1 < dis2)
            r = m2;
        else
            l = m1;
    }
    return {getDistance(x, l, points), l};
}

double ternarySearchX(const vector<Point>& points){
    double l = -MAX, r = MAX;
    while (r - l > EPS){
        double  m1 = l + (r-l)/3,
                m2 = r - (r-l)/3;

        double dis1,y1,dis2,y2;
        tie(dis1, y1) = ternarySearchY(m1, points);
        tie(dis2, y2) = ternarySearchY(m2, points);

        if(dis1 < dis2)
            r = m2;
        else
            l = m1;
    }
    return l;
}

// gets the point that minimizes the total distance from all given points
Point getCentralPoint(const vector<Point>& points){
    double x = ternarySearchX(points);
    return {x, ternarySearchY(x, points).second};
}

int main() {
    int t;
    cin >> t;
    while (t--){
        int n;
        cin >> n;
        int x, y;
        vector<Point> points;
        for (int i = 0; i < n; ++i) {
            cin >> x >> y;
            points.push_back({(double)x, (double)y});
        }
        Point ans = getCentralPoint(points);
        cout << fixed << setprecision(7) << ans.x << ' ' << ans.y;
    }

    return 0;
}

详细

Test #1:

score: 100
Accepted
time: 0ms
memory: 3560kb

input:

1
3
-3 0
0 3
3 0

output:

0.0000000 1.7320509

result:

ok OK!

Test #2:

score: -100
Wrong Answer
time: 66ms
memory: 3756kb

input:

10
3
-3 0
0 3
3 0
2
-1000000 1000000
-1000000 999999
3
-999999 1000000
-1000000 999999
1000000 -1000000
3
-999999 5
4 999999
999998 -999999
30
-6 15
-3 -21
2 12
1 -2
-27 -22
-3 -3
-11 0
-4 16
30 -24
-28 16
9 11
16 30
-28 -11
8 16
-30 28
23 10
-5 -11
28 10
-11 -2
30 -4
11 -17
-12 0
-5 -3
24 -13
22 -1...

output:

0.0000000 1.7320509-1000000.0000000 999999.9443672-999999.2113115 999999.2113491-211322.1414704 211327.97840181.9375201 1.8095433999905.7293664 -999901.241955023.8372304 -9.4509022-23.3389991 6.3978416-38.1535590 -11.419562818.3306724 -17.3767313

result:

wrong output format Expected double, but "1.7320509-1000000.0000000" found