蓝桥每日一题2023.10.12

港控/mmm° 2024-02-22 07:01 43阅读 0赞

[平面切分 - 蓝桥云课 (lanqiao.cn)][- _ _lanqiao.cn]

### 题目描述 ###

![b7818a7c177d403d91d897b8dd0622d5.png][]

### 题目分析 ###

每读入一条边与集合中其他边联立求解方程组，统计节点个数（当前边与其他边相连多出了几个交点）

**多出来的面就为节点个数 + 1**

我们如何判断交点的个数：我们直到两条直线平行时不相交

当斜率不相等，也就是a不相等时处于非平行状态

我们知道直线方程为y = kx + b,题中就相当于y = ax + b

如果两个直线相交我们可以联立方程

y1 = a1x1 + b1

y2 = a2x2 + b2

由于两直线有交点故x1 = x2, y1 = y2

故a1x + b1 = a2x + b2

x(a1 - a2) = b2 - b1

x = (b2 - b1) / (a1 - a2)

y = a1 \* x + b1

为了防止有精度问题我们可以写成

y = a1 \* （(b2 - b1) / (a1 - a2)） + b1

用set将x与y加入，以防止重复计算多个节点导致结果错误

解释：line.insert(a, b).second就是用来判断为a, b值的这条边前面有无出现过，出现过就不用重复加入

注： 最开始有一个面，也就是在没有线的时候ans需要初始化为1

#include<bits/stdc++.h>
    using namespace std;
    typedef pair<double, double> PII;
    int n, ans = 1;
    double a, b;
    set<PII> line;
    int check(double a, double b)
    {
        set<PII> num;
        for(auto lines : line)
        {
            if(a != lines.first)//不平行会有交点 
            {
                double x = (lines.second - b) * 1.0 / (lines.first - a);
                double y =  a * ((lines.second - b) * 1.0 / (lines.first - a))  + b * 1.0;
                num.insert({x, y});
            }
        }
        return num.size();
    }
    int main()
    {
        cin >> n;
        for(int i = 1; i <= n; i ++)
        {
            cin >> a >> b;
            if(line.insert({a, b}).second)
            {
                ans += check(a, b) + 1; 
            }
        }
        cout << ans << '\n';
        return 0;
    }

[- _ _lanqiao.cn]: https://www.lanqiao.cn/problems/503/learning/?first_category_id=1&page=1&sort=students_count&second_category_id=3&name=%E5%B9%B3%E9%9D%A2%E5%88%87%E5%88%86
[b7818a7c177d403d91d897b8dd0622d5.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/02/22/d20b12ddd016490886fa5aadaf69a1fe.png