面试算法题*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\pir}{n} > r$ 解出 $n$ 最多 $6$。

My solution for T2

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