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 这道题目可以使用线段树来解决。首先，我们需要定义一个线段树节点的数据结构，其中包含了直线的斜率和截距，以及左右子节点的指针。
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 于 2023-8-22 16:46 编辑
题目描述：
小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;
}
}
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;
if (count == 0) {
lines.erase(line);
count.erase(line);
}
}
}
}
}
return 0;
}
如果回答对你有帮助，请给我一个最佳答案！{:10_254:}{:10_254:}{:10_254:}
现在孩子知道题的思路了，这玩意斜率是什么 《论直角坐标系中一次函数的斜率该如何求取》 看题解明白了，不用回复了 难度？ sfqxx 发表于 2023-8-22 19:31
难度？
不大
会了
页:
[1]