#P7432. 保卫艾尔

    ID: 7446 传统题 1000ms 256MiB 尝试: 3 已通过: 2 难度: 8 上传者: 标签>计算几何扫描线组合数学CF2500线段树矩阵递归构造

保卫艾尔

保卫艾尔

时间限制:2s,空间限制:512MB

题目背景

在黑暗之神埃蒙被消灭之后,他的爪牙仍然死心不改,决定集结最后的大军,一举进攻艾尔。

亚顿之矛上,察觉到这些异动的星灵大主教阿塔尼斯十分无奈地和相位技师凯莱克斯交流。

“凯莱克斯,大战就要来临了,可是艾尔的防御工事还没有准备好。”“没关系大主教,我刚刚研制出了一种新型的建造防御矩阵的方法bulabulabula这样一来,我们就能更加有效地抵御埃蒙爪牙的入侵。”

“好,那么你就去办吧,记住,一定要把防御矩阵的功效最大化。”“没问题,大主教。”

“哦对了,你最好能计算出有多少个地点能作为防御矩阵的中心,这样我们就能让圣堂武士们战斗时更加有信心。”“嗯......虽然不是很简单但还是没有问题,我尽力去办。”

“顺便一提,如果能计算出我们有多少种建立防御矩阵的方法那就更好了,我要让埃蒙的爪牙知道,在我阿塔良辰的地盘里有多少种方法能弄死他们。”“大主教......这......”

“不必多礼,现在,我们都是圣堂武士了,党相信你们。”大主教转身离去,留下了一个伟岸的背影。

“人类有句话叫什么来着,我真是哔了跳虫了。”凯莱克斯一脸辛酸地说,他觉得这个任务对他来说有点困难了,因为星灵的数学并不太好,即使是高级相位技师也是。

“不过人类里好像有一种单位能办到。”凯莱克斯立刻折跃到克哈,找到了你来帮助他完成这个任务。

题目描述

凯莱克斯研制出的新防御矩阵系统的建立方式是这样的:他用艾尔上的n座水晶塔为基础建立多层防御矩阵,如果将艾尔视为一个直角坐标系,则每座水晶塔都有一个坐标(xi ,yi)。

一层防御矩阵是一个四边形,四边形的四个顶点都是一座水晶塔,而且四边形两条对角线分别平行于x轴和y轴。两条对角线的交点为防御矩阵的中心。中心必须位于防御矩阵的内部,同时也不能位于四边形的边上(即该四边形是一个严格的凸四边形)。注意,防御矩阵的中心不一定有水晶塔。

一个防御矩阵系统由多层防御矩阵组成,一个系统内的所有的防御矩阵都拥有相同的中心,且任意两个四边形不能相交。现在,凯莱克斯想让你帮他计算大主教给他的三个问题:

  1. 如果把层数最多的防御矩阵系统称为最优系统,那最优系统有多少层防御矩阵?

  2. 有多少个地点可以作为最优系统的中心?

  3. 有多少种建立最优系统的方案?

当然如果你觉得这些问题比较难可以先回答其中的一个或者两个。

输入格式

第一行两个正整数 n,tyn,ty,表示水晶塔数量和需要回答的问题数量,ty∈{1,2,3}ty\in\{1,2,3\}。

接下来 nn 行,每行两个整数 xi,yix_i,y_i,表示第 ii 座水晶塔的坐标。

输出格式

一行输出 tyty 个整数:第一个数为最优系统的层数;当 ty≥2ty\ge2 时输出最佳中心位置数量;当 ty=3ty=3 时再输出建立最优系统的方案数。

第二、三个数均对 109+710^9+7 取模。

样例输入1

13 3
1 3
2 3
3 1
4 1
3 2
4 2
3 4
3 5
4 4
4 5
4 3
5 3
6 3

样例输出1

2 2 4

样例解释

样例如下图:

原题示意图

两个最佳选址点分别为(3, 3)和(4, 3)。

数据范围

本题有 1010 个测试点,各点范围如下。所有 tyty 均在 {1,2,3}\{1,2,3\} 中。

测试点 tyty nn 上限 坐标范围
1 5000 1≤xi,yi≤50001\le x_i,y_i\le5000
2
3
4 1 5×1045\times10^4 1≤xi,yi≤5×1041\le x_i,y_i\le5\times10^4
5 2
6 3
7 1 5×1055\times10^5 −109≤xi,yi≤109-10^9\le x_i,y_i\le10^9
8 2
9、10 3