QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#201361 | #7336. Factory | QuanQiuTong | AC ✓ | 0ms | 1632kb | C++14 | 1.4kb | 2023-10-05 13:57:05 | 2023-10-05 13:57:06 |
Judging History
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!