题目描述
小 C 喜欢在画板上画画。他进行了 n 次操作,每次操作有如下三种可能:
1 k b
代表小 C 绘制了一条解析式为 y=kx+b 的直线。
2 k b
代表小 C 询问你直线 y=kx+b 与多少条被绘制的直线有恰好一个公共点。
3 k b
代表小 C 擦除所有与直线 y=kx+b 有至少一个公共点的直线。
注意:两条重合的直线有无数个交点。
注意:询问时重合的直线应分别计算。
输入格式
第一行一个整数 n。
接下来 n 行,每行三个整数 1/2/3,k,b,代表一次操作。
输出格式
对每次 2 k b
操作,输出满足要求的直线数量。
提示
【样例 1 解释】
第 1 次操作,绘制直线 y=x。
第 2 次操作,绘制直线 y=−x。
第 3 次操作,可以发现直线 y=2x+1 与前两条线相交。
第 4 次操作,擦掉所有 y=x+3 相交的线,直线 y=−x 被擦掉。
第 5 次操作,y=2x+1 显然与 y=x 相交。
第 6 次操作,y=x+1 与 y=x 斜率相等,是平行线,不相交。
【数据范围】
对于 100% 的数据,1≤n≤105,1≤∣k∣≤105,0≤∣b∣≤105。
提示:本题开启捆绑测试。
Subtask12345Sp. Constraintsn≤5000∣k∣,∣b∣≤50无第 3 类操作第 i 次操作满足 k=i无特殊限制Score2721131425在赛后新添加的 hack 测试点将放入 subtask 6。
题目来源
项目 |
人员 |
idea |
船酱魔王 |
data |
check |
EstasTonne |
solution |
船酱魔王 |