QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#201361#7336. FactoryQuanQiuTongAC ✓0ms1632kbC++141.4kb2023-10-05 13:57:052023-10-05 13:57:06

Judging History

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

  • [2023-10-05 13:57:06]
  • 评测
  • 测评结果:AC
  • 用时:0ms
  • 内存:1632kb
  • [2023-10-05 13:57:05]
  • 提交

answer

#include <cstdio>
#include <cmath>
#define read() ({int x,c,f=1;while((c=getchar())<48||57<c)if(c=='-')f=-1;for(x=c^48;47<(c=getchar())&&c<58;)x=x*10+(c^48);x*f; })

using ll = long long;
typedef struct vec
{
    double x, y;
    double operator*(const vec &rhs) const { return x * rhs.x + y * rhs.y; }
    vec operator+(const vec &rhs) const { return {x + rhs.x, y + rhs.y}; }
    vec operator-(const vec &rhs) const { return {x - rhs.x, y - rhs.y}; }
    vec operator*(double p) const { return {x * p, y * p}; }
    vec operator/(double p) const { return {x / p, y / p}; }
} point;
double len(const vec &v) { return sqrt(v * v); }
double dis(point a, point b) { return len(a - b); }
point p[1003];

void solve()
{
    int n = read();
    point ans = {0, 0}, las = {1e18, 1e18};
    for (int i = 1; i <= n; ++i)
        p[i] = vec{(double)read(), (double)read()}, ans = ans + p[i];
    ans = ans / n;
    double exp_dis = 0;
    for (int i = 1; i <= n; ++i)
        exp_dis += dis(ans, p[i]);
    while (dis(ans, las) / exp_dis > 3e-7)
    {
        double f = 0;
        for (int i = 1; i <= n; ++i)
            f += 1 / dis(p[i], ans);
        point t = {0, 0};
        for (int i = 1; i <= n; ++i)
            t = t + p[i] / dis(p[i], ans);
        las = ans, ans = t / f;
    }
    printf("%.9lf %.9lf\n", ans.x, ans.y);
}
int main()
{
    for (int t = read(); t--;)
        solve();
}
/*
1
3
-3 0
0 3
3 0
*/

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

input:

1
3
-3 0
0 3
3 0

output:

0.000000000 1.732046125

result:

ok OK!

Test #2:

score: 0
Accepted
time: 0ms
memory: 1608kb

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.000000000 1.732046125
-1000000.000000000 999999.500000000
-999998.942589160 999998.942589160
-211321.869479965 211327.674002903
1.937655595 1.809783837
999905.726858186 -999901.242621541
23.828397882 -9.446867334
-23.295356716 6.406485397
-38.083020295 -11.430405848
18.380501104 -17.245340345

result:

ok OK!

Test #3:

score: 0
Accepted
time: 0ms
memory: 1516kb

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.000000000 1.732046125
-1000000.000000000 999999.500000000
-999998.942589160 999998.942589160
-211321.869479965 211327.674002903
-6.249999153 2.472577896
999915.810637852 -999901.142144643
-22.820166503 26.212410184
6.561275060 -4.941093020
28.760103450 5.162752319
-13.824383924 -39.425623962

result:

ok OK!

Test #4:

score: 0
Accepted
time: 0ms
memory: 1604kb

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.000000000 1.732046125
-1000000.000000000 999999.500000000
-999998.942589160 999998.942589160
-211321.869479965 211327.674002903
-4.104560404 -4.798706117
999899.266177921 -999904.210857753
3.714026296 18.766453299
-15.415543153 27.651201065
5.141167862 -12.115741828
-42.911682305 -38.319978477

result:

ok OK!

Test #5:

score: 0
Accepted
time: 0ms
memory: 1540kb

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.000000000 1.732046125
-1000000.000000000 999999.500000000
-999998.942589160 999998.942589160
-211321.869479965 211327.674002903
-0.204409162 -8.398300345
999894.564459108 -999905.993230575
-20.542220164 1.449689336
-24.260122700 0.298106375
7.893382934 -20.645090645
24.037668958 76.548674400

result:

ok OK!

Test #6:

score: 0
Accepted
time: 0ms
memory: 1544kb

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.000000000 1.732046125
-1000000.000000000 999999.500000000
-999998.942589160 999998.942589160
-211321.869479965 211327.674002903
-5.569863561 -1.954769269
999902.606301402 -999893.230328972
4.511489493 12.049732780
1.159883894 10.063327115
24.244753324 8.646936622
-33.361196508 39.504971327

result:

ok OK!

Test #7:

score: 0
Accepted
time: 0ms
memory: 1632kb

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.000000000 1.732046125
-1000000.000000000 999999.500000000
-999998.942589160 999998.942589160
-211321.869479965 211327.674002903
3.000007544 -9.000002164
999885.995529998 -999902.965016524
4.949271793 -1.748673376
0.742976752 -25.047203047
20.539255897 -20.060042583
-6.407317567 16.701278401

result:

ok OK!