EOJ 2616 游黄山

EOJ 2616 游黄山

/

分别对x和y利用前缀和求带权中位数。这类题不是经常遇到，所以记录一下。

#include <bits/stdc++.h>
using namespace std;struct Point
{double x, y, w;
}p[105];
double sum[105];bool cmpx(const Point &a,const Point &b)
{return a.x < b.x;
}
bool cmpy(const Point &a,const Point &b)
{return a.y < b.y;
}int main()
{int t, n;cin >> t;while(t--){scanf("%d", &n);for(int i = 0; i < n; ++i)scanf("%lf %lf %lf", &p[i].x, &p[i].y, &p[i].w);sort(p, p+n, cmpx);sum[0] = p[0].w;for(int i = 1; i < n; ++i)sum[i] = sum[i-1] + p[i].w;double tot = sum[n-1], x, y;for(int i = 0; i < n; ++i){double left = (i ? sum[i-1] : 0);double right = sum[n-1] - sum[i];if(left <= tot/2 && right <= tot/2){x = p[i].x;break;}}sort(p, p+n, cmpy);sum[0] = p[0].w;for(int i = 1; i < n; ++i)sum[i] = sum[i-1] + p[i].w;for(int i = 0; i < n; ++i){double left = (i ? sum[i-1] : 0);double right = sum[n-1] - sum[i];if(left <= tot/2 && right <= tot/2){y = p[i].y;break;}}double ans = 0;for(int i = 0; i < n; ++i)ans += p[i].w * (fabs(p[i].x - x) + fabs(p[i].y - y));printf("%.6f %.6f %.6fn", x, y, ans);}return 0;
}