梯形阵
时间限制：50s 空间限制：512MB
题目描述
小Q最近喜欢上了一款游戏，名为《舰队connection》，在游戏中，小Q指挥强大的舰队南征北战，从而成为了一名
dalao。在战斗中，布阵往往是决定胜败的关键，其中梯形阵捉摸不定的攻守能力深受小Q喜爱。
【题意描述】
小Q的舰队有n艘船在海上航行，每艘船都拥有自己的坐标(xi,yi)。我们规定x表示行，y表示列，x从上到下增加，
y从左到右增加，左上角为(1,1)，右下角为(Xmax, Ymax)。梯形阵由舰队中的至少4艘船构成，阵中的所有船只都
在一条直线上，且刚好与坐标轴夹角为45度。阵型中所有船只组成的线段上不能有其他的船只，但延长线上可以有
其他船只。例如，在以下阵列中(.表示海，*表示船)
.*.**.
*.***.
.*.*..
**..*.
*..*.*
....*.
存在6种梯形阵，其中3种如下(被X标注的为阵中的船只)：
.*.**..*.X*..*.*X.
X.***.*.X**.*.*X*.
.X.*...X.*...*.*..
**..*.X*..*.*X..*.
*..X.**..*.*X..*.*
....X.....*.....*.
另外的3种均在同一条直线上，但它们被视为不同的梯形阵，如下：
.X.**..*.**..X.**.
*.X**.*.X**.*.X**.
.*.X...*.X...*.X..
**..X.**..X.**..X.
*..*.**..*.X*..*.X
....*.....*.....*.
需要注意的是，以下三种不被认为是梯形阵，因为它们所在线段上包含了其他船只。
（X表示选出的船只，#表示不合法的其他船只）
.X.**..X.**..X.**.
*.#**.*.X**.*.X**.
.*.X...*.#...*.X..
**..X.**..X.**..#.
*..*.X*..*.X*..*.X
....*.....*.....*.
小Q会不断给出两种询问(type, L, R, k)
询问1：在L<=xi<=R的所有船中，至少由1/k的船组成的梯形阵有多少种
询问2：在L<=yi<=R的所有船中，至少由1/k的船组成的梯形阵有多少种
例如，在上图的舰队中：
.*.**.
*.***.
.*.*..
**..*.
*..*.*
....*.
对于询问(1,1,5,3)来说，1~5行共计15艘船，至少由其中1/3的船即5艘船组成的梯形阵只有1种。
对于询问(1,1,5,4)来说，至少由1/4的船，即15/4艘船组成的梯形阵，由于船必须是整数艘
也即至少4艘船组成，有5种。
对于询问(2,2,5,6)来说，2~5列共计12艘船，至少由1/6的船组成，即至少由2艘船组成
但是梯形阵至少要由4艘船组成，所以只有1种。
输入格式
第一行三个数，n, Xmax, Ymax，空格分隔，表示船数和最大坐标。
接下来n行，每行两个数Xi, Yi，空格分隔，表示每艘船的位置。
接下来1行，一个数q，表示任务2的询问个数。
接下来q行，每行4个数type, L, R, k，空格分隔，描述一个询问。
n<=200000，1<=Xmax<=500000，1<=Ymax<=500000，1<=q<=100000，1<=k<=n
所有询问k之和不超过200000
输出格式
共计q行，每行一个数，表示每个询问的答案。
样例输入
16 6 6 1 2 1 4 1 5 2 1 2 3 2 4 2 5 3 2 3 4 4 1 4 2 4 5 5 1 5 4 5 6 6 5 3 1 1 5 3 1 1 5 4 2 2 5 6
样例输出
1 5 1
提示
没有写明提示
题目来源
没有写明来源