所谓的三分套三分 ， 题意RT
#include<iostream> #include<algorithm> #include<fstream> #include<string> #include<cmath> #include<cstring> #include<vector> #include<map> #include<set> #include<queue> #include<stack> #include<sstream> #include<cstdio> #define INF 0x3f3f3f3f #define inf 0x7FFFFFFF #define MOD 100 #define pii pair<int,int> #define eps 1e-6 #define equals(a,b) (fabs(a-b)<eps) #define bug puts("bug") #define re register const int maxn = 1e6 + 5; const double PI = acos(-1.0); typedef long long ll; using namespace std; struct Point { double x, y; Point(){} Point(double _x,double _y):x(_x),y(_y){} }; Point p[105]; int n; double get_sum(double xx,double yy) { double res = 0; for (int i = 0; i < n; i++) res += sqrt((xx - p[i].x) * (xx - p[i].x) + (yy - p[i].y) * (yy - p[i].y)); return res; } double three(double x) { double l = 0.0, r = 10000.0; for (int i = 0; i < 100; i++) { double mid = (l + r) / 2; double mmid = (mid + r) / 2; if (get_sum(x, mid) < get_sum(x, mmid)) r = mmid; else l = mid; } return get_sum(x, l); } int main() { while (~scanf("%d", &n)) { for (int i = 0; i < n; i++) scanf("%lf %lf", &p[i].x, &p[i].y); double l = 0.0, r = 10000.0; for (int i = 0; i < 100; i++) { double mid = (l + r) / 2; double mmid = (mid + r) / 2; if (three(mid) < three(mmid)) r = mmid; else l = mid; } printf("%.0f\n", three(l)); } return 0; }