【题解】P8720 题解

liangbob · 2023-06-14 07:48:22 · 题解

P8720 题解

思路分析

小学几何题。

几何题没有图，我不是很满意。

我们先来证明一个结论：设平面在加入某不重合于已有线后与原已有线交点数为 x，则该平面会增加 x + 1 个部分。

证明如下：

这个线产生 x 个交点，我们把它单独拎出来看一下。

可以看到，黑线上被红色点截，会出现 x + 1 段线段。

而这些线段，经过的刚好就是一个部分，刚好把这个部分从一个变成了两个，部份数加了一。

每条线段都一样，所以会增加 x+1 个部分。

证毕。

接着，我们再来证明一个结论：

直线 y=k_1x+b_1 与 y = k_2x+b_2 的交点横坐标为 \dfrac{b_2-b_1}{k_1-k_2}，纵坐标为 k_1 \cdot \dfrac{b_2-b_1}{k_1-k_2} +b_2。

话不多说，先上图：

中间的小点就是交点。

可以看到，这个交点 x 轴与 y 轴是相同的。所以可以联立两个式子为方程组，得：

将 ② - ① 得：

将 x=\dfrac{b_2-b_1}{k_1-k_2} 代回原式：

证毕。

有这两个结论后，我们就可以思考一下方法了：

1. 直线去重。这是显然的，毕竟重复的会多算。
2. 枚举每一条线，计算其与之前线的交点。注意交点也要去重。注意：如果枚举到两条线斜率一致，就要过掉。因为它们没有交点。
3. 答案加上交点数加一，回到步骤二。

依照步骤实现即可。去重可以用 set。然后注意结果加一（平面初始就是一部分）。

代码

#include <iostream>
#include <map>
#include <set>
#define IL inline
using namespace std;
const int N = 1e5 + 10;

struct node
{
    long double k, b;
}a[N];

int main()
{
    int n;
    cin >> n;
    int m = 0;
    set<pair<long double, long double> > p;
    for(int i = 1;i <= n;i++)
    {
        long double x, y;
        cin >> x >> y; 
        p.insert({x, y});//set 去重。 
    }
    for(auto i = p.begin();i != p.end();i++) //遍历并存入结构体数组。 
    {
        a[++m] = {(*i).first, (*i).second};
    }
    int ans = 0;

    for(int i = 1;i <= m;i++)
    {
        set <pair<long double,long double> > o;
        for(int j = 1;j < i;j++)
        {
            long double k1 = a[i].k;
            long double k2 = a[j].k;
            long double b1 = a[i].b;
            long double b2 = a[j].b;
            if(k1 == k2) continue; //斜率一致，平行，过掉。 
            long double x1 = (b2 - b1)  / (k1 - k2);
            long double y1 = k1 * x1 + b1;
            //根据公式计算交点。
            o.insert({x1, y1});
            //加入 set 去重。
        }
        ans += (o.size() + 1);
    }
    cout << ans + 1 << endl; //初始有一部分，要加一。
    return 0;
}