QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#261258 | #7336. Factory | gondozu | AC ✓ | 66ms | 3768kb | C++20 | 1.9kb | 2023-11-22 19:33:49 | 2023-11-22 19:33:50 |
Judging History
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!