#1659. 「CERC2018」Incredible Hull

「CERC2018」Incredible Hull

题目描述

译自 CERC 2018F. Incredible Hull

在一个皇家赌场中,有一个放有很多老虎机的大房间。赌场老板感觉这个房间结构太简单,这样的话赌徒就有很大机会在没输掉那么多钱之前就离开房间。房间结构需要是固定的,因此老板设计了一个复杂的老虎机摆放和过道设计方式,这样的话人们就更容易在里面迷路了。

房间的形状大致是椭圆形的。如果房间是空的,从房间内部的任何点看,整个房间都可以被看到。房间中的 NN 台老虎机每台都可以看做一个点,并且每台都有一个特殊的利润值,每两台老虎机利润值互不相同。老板想要这些老虎机通过过道按下面的方式连通。

已经至少有三台老虎机被建在房间的墙里了,所有这些建在墙里的老虎机必须用直的过道直接相连,以形成一个围绕整个屋子并且闭合的周长路径。房间里剩下的老虎机都在这个闭合的周长路径内部。

这个房间要被直过道分成更小的区域,每个区域都被它自己的周长路径包围。分割古城分成以下两步。

  • 第一步操作如下。如果在周长路径上有至少四台老虎机,就要选出两台老虎机作为枢纽。第一台是在周长路径上收益最多的那台老虎机;第二台也在周长路径上,并且距离第一台枢纽老虎机最远。两台老虎机之间的距离用周长路径描述,它等于从一台老虎机到另一台老虎机所经过的过道条数。如果有两台最远的老虎机,那么第二台枢纽老虎机为收益最大的老虎机。周长路径内部的区域被一条连接着这两台枢纽老虎机的过道分成两部分。这两个新形成的小区域的周长路径是包围着这片区域的原周长路径和这条新过道。这个过程重复进行,直到不能新建出新的区域为止;
  • 当前一个过程结束后,第二个分割过程开始。这个过程操作如下。对于任意内部没有过道的区域 AA,考虑在那个区域内部的所有老虎机。如果有,就在收益最多的那台老虎机与所有在 AA 的周长路径 PAP_A 上的老虎机之间建一条过道。这就将这个区域分割成了一些小区域。每个新区域的周长路径包含 PAP_A 中的一条过道和两条新建的过道。这个过程重复进行,直到不能新建出新的区域为止。

赌场老板想要估计他的设计的利润能力。为了计算,他定义了一个所谓的高收益配置。这个配置是一个最大的老虎机的集合,属于集合的任意两台老虎机都被一条过道直接相连。

这个老板对三个盈利参数十分感兴趣。第一个盈利参数是一个高收益配置的大小,第二个参数是这个设计里高收益配置的个数,第三个参数是至少属于一个高收益配置的老虎机个数。

输入格式

第一行包含一个整数 NN,表示老虎机数目。

接下来 NN 行,每行两个整数 X,YX,Y,表示一台老虎机在房间里的位置。所有老虎机按利润值递减的顺序给出,没有任何三台老虎机共线。

输出格式

输出三个盈利参数。

样例 1

6
8 2
6 8
4 9
3 5
3 0
1 5
4 1 4
6
1 1
6 1
1 6
6 6
3 2
4 5
4 2 6

数据范围与提示

3N105,0X,Y1093\le N\le 10^5,0\le X,Y\le 10^9