QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#201353 | #7336. Factory | QuanQiuTong | TL | 0ms | 1512kb | C++14 | 1.3kb | 2023-10-05 13:54:16 | 2023-10-05 13:54:18 |
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;
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...