P8720 [蓝桥杯 2020 省 B2] 平面切分 题解

· · 题解

前言

建议本题评黄，因为需要较强的数学能力。
如果格式炸了去这里看哦。

题意

给出 N 条直线的解析式 y=kx+b，求出这些直线把平面分成了几部分。

思路

看到这道题我们会梦回小学五年级在某场考试或某张毒瘤数学试卷里做到的题目（本来在这里有一个好康的美化，但是管理大大告诫我不要用，所以还是点链接吧）：

已知 1 条直线可以把平面最多分成两部分，2 条直线可以把平面最多分成 4 部分，3 条最多可以分成 7 部分，请问 4、5 条直线最多可以把平面分成几部分？

回忆一下我们当时是如何做出这样的题目的？找规律？画图？蒙答案？

或者我们可以重复这样的步骤。

以上推断均保证没有三线共点或平行的情况。
仔细阅读加粗部分显然可以发现，每增加 n 个交点，会多出 n+1 个部分。
我们就成功的把求几部分的问题转化成了求交点的问题。

接着考虑 三点共线 和 平行 的情况。

对于三点共线，若一条直线于另两条直线的交点交在一起 （注意我的表述方式），因为这一点之前已经分出了它所对应的部分，所以不需要再次统计。
对于一对直线平行，则仅对这两条直线来说，它们没有任何交点，因此这对直线不需要计算交点。

综上所述，我们只要模拟以上过程，不断添加一条一条直线并且计算交点个数即可。

代码

#include <iostream>
#include <set>
#include <vector>

#define i64 long long
#define reg register
#define qwq puts("fzy qwq ~");
#define pb push_back
#define Line pair<double, double>
#define kk first
#define bb second

using namespace std;

int n, tmp, ans = 1;
double xk, xb, k1, k2, b1, b2;
set<Line> l;
vector<int> k, b;

void init()
{
    for (reg int i = 1; i <= n; ++i)
    {
        scanf("%lf%lf", &xk, &xb);
        l.insert(make_pair(xk, xb)); // 使用 set 去重并顺手排序
    }
    for (reg auto x : l)
        k.pb(x.kk), b.pb(x.bb);      // 将直线放回 vector O(1) 访问降低常数
}

int main()
{
    scanf("%d", &n);
    init();

    Line p;
    for (reg int i = 0; i < (int)k.size(); ++i) //枚举每一条直线
    {
        set<Line> pos;                          // 交点的集合
        for (reg int j = i - 1; j >= 0; --j)
        {
            k1 = k[i], b1 = b[i],
            k2 = k[j], b2 = b[j];
            if (k1 == k2) continue;             // 平行，直接计算下一条直线
            p.kk = (b2 - b1) / (k1 - k2);       // 求得交点
            p.bb = k1 * ((b2 - b1) / (k1 - k2)) + b1; // 
            pos.insert(p);
        }
        ans += pos.size() + 1;                  // 添加新分出的部分
    }
    printf("%d\n", ans);
    return 0;
}

由于使用了 STL 不吸氧达到了 850ms here。
开启 O2 优化为 205ms 成为目前最优解 here。