#P18499. Beer Circuits

Beer Circuits

Beer Circuits

美丽的 Delft 市有 nn 家酒吧,在二维地图上分别用一个点表示。大学新生们常常组织一条喝酒回路:选择若干家酒吧并安排一个访问顺序,依次到每家喝一杯,最后从最后一家回到起点。

只去两家太无聊,因此一条回路至少访问 3 家不同酒吧,最多访问 kk 家不同酒吧;回到起点不算重复选取一家新酒吧。回路中的访问酒吧两两不同,最后再回到第一家。

喝过酒后走太远会很累。组织者首先希望让回路中相邻两家酒吧间欧几里得距离的最大值尽量小,这里也包括最后一家回到起点的那一段。每到下一家后大家都会精神一振,所以总步行距离并不重要。

在上述最大相邻距离最小的所有回路中,组织者进一步只选择访问酒吧数最少的回路。

求这样的最优回路有多少种。访问的酒吧集合不同,或者访问顺序不同,就认为回路不同。即使其它次序相同,只是起点酒吧不同,也认为是不同回路;相反方向的访问次序也不同。

输入格式

第一行两个整数 n,kn,k(3≤n≤200 0003\le n\le200\,000,3≤k≤303\le k\le30)。kk 可以大于 nn。

接下来 nn 行,每行两个整数 x,yx,y(0≤x,y≤1090\le x,y\le10^9),表示一家酒吧的坐标。

保证没有两家酒吧位于完全相同的位置。

输出格式

输出三行:

  1. 第一行一个整数,表示最优回路中最大相邻欧几里得距离的平方。两点平方距离是 (Δx)2+(Δy)2(\Delta x)^2+(\Delta y)^2。
  2. 第二行一个整数,表示在最小化上述最大距离后,最少访问的酒吧数。
  3. 第三行一个整数,表示同时满足两个最优条件的回路方案数。答案不取模。

原样例 1

3 3
0 0
2 2
1000000000 1000000000
2000000000000000000
3
6

原样例 2

8 5
5 5
5 7
7 7
3 7
2 5
8 5
3 4
7 4
5
5
20

原样例2:红色的两条五点回路

图中红色边表示组织者想选择的两条回路:它们都经过中间的两家酒吧,一条走左半部分,另一条走右半部分,每条恰好包含 55 家酒吧。每条回路可以选择 55 个起点和 22 个方向,共 1010 种访问次序,因此总共 2020 种。

这个样例中也存在经过全部 88 家酒吧、且最大相邻距离相同的回路,但它的酒吧数不是最少,因此不计入答案。