平面切分

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

题目描述

平面上有 N 条直线, 其中第 i条直线是 y=Ai*x+Bi。

请计算这些直线将平面分成了几个部分。

输入格式

第一行包含一个整数 N。

以下 N行, 每行包含两个整数 Ai,Bi。

输出格式

一个整数代表答案。

样例 #1

样例输入 #1

3
1 1
2 2
3 3

样例输出 #1

6

提示

对于 $50 %$ 的评测用例, 1<=n<=4,-10<=Ai,Bi<=10。

对于所有评测用例, 1<=n<=1000,-1e5<=Ai,Bi<=1e5。

理解

• 当没有任何直线时，显然平面只有一部分。
• 当有 11 条直线时，平面有 22 个部分。
• 当有 22 条直线时，第 22 条直线交第 11 条于一个点，所以增加了 22 个部分，共 44 个部分。
• 当有 33 条直线时，第 33 条直线交前两条各于一个点，所以又增加了 33 个部分，共 77 个部分 （假设没有三线共点或平行）。
• 当有 44 条时，增加 33 个交点，44 个部分，共 1111 个部分。
• 当有 55 条时，增加 44 个交点，55 个部分，共 1616 个部分。

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

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

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

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

代码

#include <iostream>
#include<cstdio>
#include <sstream>
#include<algorithm>
#include<cmath>
#include<string>
#include<set>
#define PII pair<long double,long double>

using namespace std;
PII pos;
int n;
const int N=1e3+10;
long double a[N],b[N];
bool vis[N];
int main()
{
   cin>>n;
   long long res=0;
   for(int i=1;i<=n;i++)
   {
       cin>>a[i]>>b[i];
       set<PII> s;
       s.clear();
       for(int j=1;j<i;j++)
       {
           if(vis[j])continue;
           if(a[i]==a[j]&&b[i]==b[j])
           {
               vis[i]=1;
               break;
           }
           if(a[i]==a[j])continue;
           s.insert({(b[i]-b[j])/(a[j]-a[i]),(a[j]*b[i]-a[i]*b[j])/(a[j]-a[i])});

       }
       if(!vis[i])
       res+=s.size()+1;
   }
   cout<<res+1<<endl;



    return 0;
}