蓝桥每日一题2023.10.12

平面切分 - 蓝桥云课 (lanqiao.cn)

题目描述

题目分析

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

多出来的面就为节点个数 + 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
using namespace std;
typedef pair<double, double> PII;
int n, ans = 1;
double a, b;
set line;
int check(double a, double b)
{
    set 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;
}