大家都是用什么爬山算法、模拟退火算法的。。。太高端了蒟蒻不会
于是Xs找到了些奇怪的东西
这篇论文的3.3节 "N孔系统"就是这道题呢~
于是就没啦≥v≤~
1 /************************************************************** 2 Problem: 3680 3 User: rausen 4 Language: C++ 5 Result: Accepted 6 Time:300 ms 7 Memory:1040 kb 8 ****************************************************************/ 9 10 #include <cstdio> 11 #include <cmath> 12 13 using namespace std; 14 typedef double lf; 15 const int N = 10005; 16 const lf eps = 1e-5; 17 18 #define P point 19 struct P { 20 lf x, y; 21 P() {} 22 P(lf _x, lf _y) : x(_x), y(_y) {} 23 24 inline P operator * (lf X) { 25 return P(x * X, y * X); 26 } 27 inline P operator / (lf X) { 28 return P(x / X, y / X); 29 } 30 inline P operator + (P a) { 31 return P(x + a.x, y + a.y); 32 } 33 34 inline bool operator == (P a) { 35 return fabs(x - a.x) < eps && fabs(y - a.y) < eps; 36 } 37 inline bool operator != (P a) { 38 return fabs(x - a.x) >= eps || fabs(y - a.y) >= eps; 39 } 40 }p[N]; 41 42 int n; 43 lf w[N]; 44 45 inline int read() { 46 int x = 0, sgn = 1; 47 char ch = getchar(); 48 while (ch < '0' || '9' < ch) { 49 if (ch == '-') sgn = -1; 50 ch = getchar(); 51 } 52 while ('0' <= ch && ch <= '9') { 53 x = x * 10 + ch - '0'; 54 ch = getchar(); 55 } 56 return sgn * x; 57 } 58 59 inline lf sqr(lf x) { 60 return x * x; 61 } 62 63 inline lf dist(P a, P b) { 64 return sqrt(sqr(a.x - b.x) + sqr(a.y - b.y)); 65 } 66 67 int main() { 68 int i; 69 lf W = 0; 70 P p1 = P(0, 0), p2 = p1, p3; 71 n = read(); 72 for (i = 1; i <= n; ++i) { 73 p[i].x = read(), p[i].y = read(), w[i] = read(); 74 p1 = p1 + p[i] * w[i], W += w[i]; 75 } 76 p1 = p1 / W; 77 while (p1 != p2) { 78 p2 = p3 = p1, p1 = P(0, 0); 79 W = 0; 80 for (i = 1; i <= n; ++i) { 81 p1 = p1 + p[i] * (w[i] / dist(p3, p[i])); 82 W += w[i] / dist(p3, p[i]); 83 } 84 p1 = p1 / W; 85 } 86 printf("%.3lf %.3lf ", p1.x, p1.y); 87 return 0; 88 }
（p.s. 这样迭代来做很快呢！）