面试算法题*2

题目描述

背景 \(k\) 聚类，可能和实际题目有出入。。。

T1

二维平面上有一个中心点 \(p_{0}\) ，你可以在上面添加一些点，但对于任意添加的两点 \(p_{i}，p_{j}\)，需满足 \(dis(p_{i},p_{0}) < dis(p_{i},p_{j})\) 且 \(dis(p_{j},p_{0}) < dis(p_{i},p_{j})\)

T2

二维平面上有 \(n+m\) 个两两不同的点，其中 \(n\) 个点我们称其为待分类点，其余的 \(m\) 个点称为中心点（分类的中心点），将一个待分类点分给中心点的代价为两点的距离。

现在给定这 \(n+m\) 个点，并且第 \(i\) 个分类只能容纳 \([l_{i},r_{i}]\) 个点，请你设计一种算法求出最小总代价最小。

My solution for T1

猜了一个等分圆，列个柿子：\(\frac{2*\pi*r}{n} > r\) 解出 \(n\) 最多 \(6\)。

My solution for T2

答了个上下界费用流，建图类似二分图带权匹配。