QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#261294 | #7336. Factory | gondozu | TL | 0ms | 0kb | C++20 | 1.9kb | 2023-11-22 19:57:26 | 2023-11-22 19:57:26 |
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 (l <= r){
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 (l <= r){
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};
}
void solveTC(){
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;
}
int main() {
int t;
cin >> t;
while (t--){
solveTC();
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 0
Time Limit Exceeded
input:
1 3 -3 0 0 3 3 0