合并果子

在一个果园里，多多已经将所有的果子打了下来，而且按果子的不同种类分成了N堆。果园是一个二维平面，第i堆果子的位置为(Xi,Yi)，重量为Wi。

多多决定把所有的果子合成一堆。每一次合并，多多可以消耗Wi (|Xi - Xj |+|Yi - Yj |)的体力把第i堆果子合并到第j堆。可以看出，所有的果子经过N-1次合并之后，就只剩下一堆了。多多在合并果子时总共消耗的体力等于每次合并所耗体力之和。

请你求出将所有果子合并成一堆消耗的总体力最少是多少。

输入描述:
第一行一个正整数N，接下来N行每行三个正整数 Xi Yi Wi

输出描述:
一个数，最少消耗的总体力

输入例子1:
4
2 1 1
1 2 3
3 1 2
2 4 2

输出例子1:
14

例子说明1:
数据约定：
20% N≤10
60% N≤1000
100% N≤100000,Xi,Yi,Wi≤100000

from collections import defaultdict

n=int(input())
d=defaultdict(int)
for i in range(n):
    t=list(map(int,input().strip().split(' ')))
    d[(t[0],t[1])]+=t[2]
ks = list(d.keys())

dxx=defaultdict(int)
for xy in d: dxx[xy[0]]+=d[xy]
kx=list(dxx.keys())
kx.sort()
left,right = 0, sum([dxx[tt]*(tt-kx[0]) for tt in kx])
dx={kx[0]:left+right}
left_cnt, right_cnt = 0, sum(dxx.values())
for i in range(1,len(kx)):
    left_cnt += dxx[kx[i-1]]
    right_cnt -= dxx[kx[i]]
    left += left_cnt*(kx[i]-kx[i-1])
    right -= right_cnt*(kx[i]-kx[i-1])
    dx[kx[i]] = left + right

dyy=defaultdict(int)
for xy in d: dyy[xy[1]]+=d[xy]
ky=list(dyy.keys())
ky.sort()
left,right = 0, sum([dyy[tt]*(tt-ky[0]) for tt in ky])
dy={ky[0]:left+right}
left_cnt, right_cnt = 0, sum(dyy.values())
for i in range(1,len(ky)):
    left_cnt += dyy[ky[i-1]]
    right_cnt -= dyy[ky[i]]
    left += left_cnt*(ky[i]-ky[i-1])
    right -= right_cnt*(ky[i]-ky[i-1])
    dy[ky[i]] = left + right

res=float('inf')
for x,y in ks:
    res=min(res, dx[x]+dy[y])
print(res)

独立求xy，对于x/y，排序，然后求一遍running sum，
但是WA，不知道哪里有bug

有个取巧的办法，分别求出大概最佳的xy，然后遍历周围的若干个点
https://www.cnblogs.com/weiyinfu/p/9488631.html