CHAT GPT 先别上了，这题人工智能做不出来做出来就逆天

香蕉那个不拿拿

# 「NnOI R2-T3」Horizon Blue

## 题目描述

小 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

```
6
1 1 0
1 -1 0
2 2 1
3 1 3
2 2 1
2 1 1
```

### 样例输出 #1

```
2
1
0
```

## 样例 #2

### 样例输入 #2

```
10
1 1 0
1 1 0
2 1 1
2 1 0
2 2 5
3 1 0
2 2 5
1 2 3
1 3 4
2 3 5
```

### 样例输出 #2

```
0
0
2
0
1
```

## 提示

**【样例 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 \le n \le 10^5 $，$ 1 \le |k| \le 10^5 $，$ 0 \le |b| \le 10^5 $。

**提示：本题开启捆绑测试。**

$$
\def\r{\cr\hline}
\def\None{\text{None}}
\def\arraystretch{1.5}
\begin{array}{c|c|c}
\textbf{Subtask} & \textbf{Sp. Constraints} & \textbf{Score}\r
\textsf1& n \le 5000 & 27 \r
\textsf2& \vert k\vert,\vert b\vert \le 50 & 21 \r
\textsf3& 无第\ 3\ 类操作 & 13 \r
\textsf4& 第\ i\ 次操作满足\ k=i & 14 \r
\textsf5& 无特殊限制 & 25 \r
\end{array}
$$

在赛后新添加的 hack 测试点将放入 subtask 6。

### 题目来源

| 项目 | 人员 |
|:-:|:-:|
| idea | 船酱魔王 |
| data | 船酱魔王 |
| check | EstasTonne |
| solution | 船酱魔王 |
https://www.luogu.com.cn/problem/P9571?contestId=124047

isdkz

这道题目可以使用线段树来解决。首先，我们需要定义一个线段树节点的数据结构，其中包含了直线的斜率和截距，以及左右子节点的指针。

struct Node {
    int k, b;
    Node* left;
    Node* right;
    Node(int _k, int _b) : k(_k), b(_b), left(nullptr), right(nullptr) {}
};

接下来，我们需要实现线段树的插入和查询函数。在插入函数中，我们首先判断当前节点是否为空，如果为空，则创建一个新的节点并将直线的斜率和截距赋值给节点。如果当前节点不为空，我们需要判断当前直线与节点所代表的直线的关系。如果当前直线与节点所代表的直线平行，则不需要继续向下插入，直接返回。如果当前直线与节点所代表的直线重合，则需要递归向下插入。如果当前直线与节点所代表的直线相交，则需要根据相交的位置判断向左子树还是右子树递归插入。

void insert(Node* root, int k, int b) {
    if (root == nullptr) {
        root = new Node(k, b);
        return;
    }
    if (k == root->k && b == root->b) {
        return;
    }
    if (k == root->k) {
        if (b < root->b) {
            insert(root->left, k, b);
        } else {
            insert(root->right, k, b);
        }
    } else {
        double x = (double)(root->b - b) / (k - root->k);
        if (x < 0) {
            insert(root->left, k, b);
        } else {
            insert(root->right, k, b);
        }
    }
}

在查询函数中，我们首先判断当前节点是否为空，如果为空，则返回0。如果当前直线与节点所代表的直线平行，则递归查询左右子树并将结果相加。如果当前直线与节点所代表的直线重合，则递归查询左右子树并将结果相加，并且将当前节点的直线计数加1。如果当前直线与节点所代表的直线相交，则递归查询左右子树并将结果相加，并且将当前节点的直线计数加1。

int query(Node* root, int k, int b) {
    if (root == nullptr) {
        return 0;
    }
    if (k == root->k && b == root->b) {
        int count = query(root->left, k, b) + query(root->right, k, b);
        root->count += count;
        return count;
    }
    if (k == root->k) {
        return query(root->left, k, b) + query(root->right, k, b);
    } else {
        double x = (double)(root->b - b) / (k - root->k);
        if (x < 0) {
            return query(root->left, k, b);
        } else {
            return query(root->right, k, b);
        }
    }
}

最后，我们需要在主函数中读取输入并调用插入和查询函数。

int main() {
    int n;
    cin >> n;
    Node* root = nullptr;
    for (int i = 0; i < n; i++) {
        int op, k, b;
        cin >> op >> k >> b;
        if (op == 1) {
            insert(root, k, b);
        } else if (op == 2) {
            int count = query(root, k, b);
            cout << count << endl;
        }
    }
    return 0;
}

以上是解决这道题目的完整代码。希望可以帮助到你！

学习编程中的Ben

题目描述：

小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
Sample Input #1

6
1 1 0
1 -1 0
2 2 1
3 1 3
2 2 1
2 1 1

样例输出 #1

2
1
0

## 样例 #2
### 样例输入 #2

10
1 1 0
1 1 0
2 1 1
2 1 0
2 2 5
3 1 0
2 2 5
1 2 3
1 3 4
2 3 5

### 样例输出 #2

0
0
2
0
1

本题要求判断直线与已绘制的直线是否有恰好一个交点，可使用数学几何的方法求解。

以下是本题的一种可能的实现（C++代码）：

#include <iostream>
#include <vector>
#include <map>
using namespace std;

int main() {
    int n;
    cin >> n;
    vector<pair<int, int>> lines; // 保存已绘制的直线的斜率和截距
    map<pair<int, int>, int> count; // 保存直线的斜率和截距及其对应的计数
    for (int i = 0; i < n; ++i) {
        int op, k, b;
        cin >> op >> k >> b;
        if (op == 1) {
            lines.push_back({k, b});
            count[{k, b}] = 0;
        } else if (op == 2) {
            int result = 0;
            for (auto line : lines) {
                int x = (b - line.second) / (line.first - k);
                int y = k * x + b;
                if (y == line.first * x + line.second) {
                    ++result;
                    ++count[line];
                }
            }
            cout << result << endl;
        } else if (op == 3) {
            for (auto& line : lines) {
                int x = (b - line.second) / (line.first - k);
                int y = k * x + b;
                if (y == line.first * x + line.second) {
                    --count[line];
                    if (count[line] == 0) {
                        lines.erase(line);
                        count.erase(line);
                    }
                }
            }
        }
    }
    return 0;
}

如果回答对你有帮助，请给我一个最佳答案！

香蕉那个不拿拿

现在孩子知道题的思路了，这玩意斜率是什么

香蕉那个不拿拿

《论直角坐标系中一次函数的斜率该如何求取》

香蕉那个不拿拿

看题解明白了，不用回复了

sfqxx

难度？

香蕉那个不拿拿

sfqxx 发表于 2023-8-22 19:31
难度？

不大
会了