QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#261258#7336. FactorygondozuAC ✓66ms3768kbC++201.9kb2023-11-22 19:33:492023-11-22 19:33:50

Judging History

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

  • [2023-11-22 19:33:50]
  • 评测
  • 测评结果:AC
  • 用时:66ms
  • 内存:3768kb
  • [2023-11-22 19:33:49]
  • 提交

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 << endl;
    }

    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 1ms
memory: 3672kb

input:

1
3
-3 0
0 3
3 0

output:

0.0000000 1.7320509

result:

ok OK!

Test #2:

score: 0
Accepted
time: 66ms
memory: 3520kb

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.9784018
1.9375201 1.8095433
999905.7293664 -999901.2419550
23.8372304 -9.4509022
-23.3389991 6.3978416
-38.1535590 -11.4195628
18.3306724 -17.3767313

result:

ok OK!

Test #3:

score: 0
Accepted
time: 66ms
memory: 3592kb

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
-22 30
0 -19
-29 -2
-7 -21
8 28
6 -5
-21 13
-28 10
-7 11
-23 -4
-22 -5
-16 -12
-20 -11
7 14
-10 -8
-25 26
4 5
-8 5
30 29
6 12
20 -17
-1 12
-10 -7
-4 4
20 -7
...

output:

0.0000000 1.7320509
-1000000.0000000 999999.9443672
-999999.2113115 999999.2113491
-211322.1414704 211327.9784018
-6.2499121 2.4727199
999915.8124977 -999901.1453861
-22.8273463 26.2169391
6.5609421 -5.0063256
28.8353378 5.1838814
-13.9118525 -39.5285654

result:

ok OK!

Test #4:

score: 0
Accepted
time: 66ms
memory: 3624kb

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
-26 -14
18 -28
16 -4
19 18
-29 -20
-23 -17
-8 -16
-5 -20
-3 21
0 -25
-30 10
16 -11
-14 -14
20 18
-15 18
-24 22
-1 -24
-4 -6
-7 9
-1 -19
-29 25
-23 1
-15 7
17...

output:

0.0000000 1.7320509
-1000000.0000000 999999.9443672
-999999.2113115 999999.2113491
-211322.1414704 211327.9784018
-4.1045309 -4.7991023
999899.2666951 -999904.2098677
3.7252993 18.7740745
-15.4487825 27.6891168
5.2633191 -12.0822289
-42.9334717 -38.4883798

result:

ok OK!

Test #5:

score: 0
Accepted
time: 62ms
memory: 3768kb

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
20 25
10 -20
-22 18
21 16
-4 -25
16 -19
2 19
6 -26
4 -14
-27 -25
24 -28
-8 -29
2 -10
4 -10
21 -21
-1 10
-11 -6
-18 7
-16 -30
10 24
-10 18
-10 -7
-29 25
-26 -...

output:

0.0000000 1.7320509
-1000000.0000000 999999.9443672
-999999.2113115 999999.2113491
-211322.1414704 211327.9784018
-0.2040920 -8.3985115
999894.5635397 -999905.9944212
-20.5499275 1.4490624
-24.3155802 0.2808753
7.9406962 -20.7413983
24.1253600 76.6447039

result:

ok OK!

Test #6:

score: 0
Accepted
time: 66ms
memory: 3604kb

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
-27 5
10 -25
-9 8
28 -4
-30 -22
-22 27
-19 -24
-2 -7
-20 3
16 -16
17 28
-3 2
27 5
7 -21
28 -27
6 -25
-28 -14
5 -14
-29 18
3 9
19 -20
-30 25
-15 26
-29 0
-30 ...

output:

0.0000000 1.7320509
-1000000.0000000 999999.9443672
-999999.2113115 999999.2113491
-211322.1414704 211327.9784018
-5.5697097 -1.9549268
999902.6058592 -999893.2290648
4.5020405 12.0476631
1.1896616 10.0298365
24.3279676 8.6753088
-33.4667552 39.6599097

result:

ok OK!

Test #7:

score: 0
Accepted
time: 66ms
memory: 3708kb

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
2 -21
23 -17
-30 27
23 17
-5 24
-23 -4
4 -20
-10 29
13 20
29 -5
-10 -29
1 28
19 -16
-19 5
-16 1
0 -21
-28 -20
-8 -19
-5 -30
29 15
18 3
13 -19
3 -9
29 20
20 -...

output:

0.0000000 1.7320509
-1000000.0000000 999999.9443672
-999999.2113115 999999.2113491
-211322.1414704 211327.9784018
3.0000000 -9.0000000
999885.9949325 -999902.9636651
4.9596035 -1.7286171
0.7504514 -25.0839108
20.5307634 -20.2004436
-6.2862659 16.8794394

result:

ok OK!