QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#201353#7336. FactoryQuanQiuTongTL 0ms1512kbC++141.3kb2023-10-05 13:54:162023-10-05 13:54:18

Judging History

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

  • [2023-10-05 13:54:18]
  • 评测
  • 测评结果:TL
  • 用时:0ms
  • 内存:1512kb
  • [2023-10-05 13:54:16]
  • 提交

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;

    while (dis(ans, las) > 1e-10)
    {
        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: 1512kb

input:

1
3
-3 0
0 3
3 0

output:

0.000000000 1.732050807

result:

ok OK!

Test #2:

score: -100
Time Limit Exceeded

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:


result: