[蓝桥杯 2020 省 B2] 平面切分
题目描述
平面上有 N N N 条直线, 其中第 i i i 条直线是 y = A i ⋅ x + B i y=A_{i} \cdot x+B_{i} y=Ai⋅x+Bi 。
请计算这些直线将平面分成了几个部分。
输入格式
第一行包含一个整数 N N N。
以下 N \mathrm{N} N 行, 每行包含两个整数 A i , B i A_{i}, B_{i} Ai,Bi。
输出格式
一个整数代表答案。
样例 #1
样例输入 #1
3
1 1
2 2
3 3
样例输出 #1
6
提示
对于 50 % 50 \% 50% 的评测用例, 1 ≤ N ≤ 4 , − 10 ≤ A i , B i ≤ 10 1 \leq N \leq 4,-10 \leq A_{i}, B_{i} \leq 10 1≤N≤4,−10≤Ai,Bi≤10。
对于所有评测用例, 1 ≤ N ≤ 1000 , − 1 0 5 ≤ A i , B i ≤ 1 0 5 1 \leq N \leq 1000,-10^5 \leq A_{i}, B_{i} \leq 10^5 1≤N≤1000,−105≤Ai,Bi≤105。
蓝桥杯 2020 第二轮省赛 B 组 I 题
思路
首先,定义几个数据类型和常量。ll
定义为long long
,pii
定义为pair<double, double>
。
读取直线的数量 n n n。然后,定义一个set
来存储所有的直线,每条直线用一个二元组(斜率和截距)表示。这里使用set
的目的是为了保证所有的直线都是唯一的,因为set
会自动删除重复的元素。接着,将set
中的直线复制到一个vector
中,方便后续的遍历。
然后,定义一个变量ans
来存储最终的结果。初始值设为2,因为一条直线至少可以将平面分为两个部分。
接下来,遍历vector
中的每一条直线,对于每一条直线,都定义一个新的set
来存储与其他直线的交点。这里使用set
的目的是为了自动删除重复的交点。
在计算交点时,首先检查两条直线是否平行,如果平行,则没有交点,直接跳过。否则,通过两条直线的斜率和截距计算出交点,并将交点添加到set
中。
最后,将set
的大小加1后加到ans
中。这是因为,每增加 n n n个交点,就会多出 n + 1 n+1 n+1个新的部分。
遍历完所有的直线后,输出ans
,这就是最终的结果。
注意
因为斜率等参数不一定是整数,应该使用 double 来存储数据,否则无法通过测试点。
AC代码
#include <algorithm>
#include <iostream>
#include <set>
#include <vector>
#define mp make_pair
#define AUTHOR "HEX9CF"
using namespace std;
using ll = long long;
using pii = pair<double, double>;const int N = 1e6 + 7;
const int INF = 0x3f3f3f3f;
const ll MOD = 1e9 + 7;int n;
set<pii> s1;
vector<pii> v1;int main() {ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);cin >> n;for (int i = 1; i <= n; i++) {double a, b;cin >> a >> b;s1.insert({a, b});}for (const auto i : s1) {v1.push_back(i);}// 一条线能分出两个部分ll ans = 2;for (int i = 1; i < v1.size(); i++) {set<pii> s2;for (int j = i - 1; j >= 0; j--) {double k1 = v1[i].first;double k2 = v1[j].first;double b1 = v1[i].second;double b2 = v1[j].second;if (k1 == k2) {// 平行,无交点continue;}// 求交点double x = (b2 - b1) / (k2 - k1);double y = k1 * x + b1;s2.insert({x, y});}// 每多n个交点,就多n+1个部分ans += s2.size() + 1;}cout << ans << "\n";return 0;
}