10、平面切分

题目 平面切分

image-04e81264

思路分析

image-e63e6d84

有一种难叫做看着就难

但通过找规律可以发现

image-3cd387d0

每加一个线 必定会加一个面

另外 这条新加的线 每与之前的一条线有交点 就另加一个面（n个交点加n）

所以就是 想办法把线都存起来 —— {k,b} 因为这里直接给了a就是k b就是b 省事得多

然后加入线的时候 检查是否已经出现过

如果出现过 就不存在

如果没出现过 就加进去 然后加一个面

加进去之后 去与之前的所有线判断是否有交点 ——使用两点相交的公式

image-50b68ad6

注意交点会有可能重合 所以这里又需要一层set

代码实现

#include<bits/stdc++.h>

using namespace std;

typedef pair<int,int> PII;

typedef pair<double,double> PDD;

set<PII> lines;

int IntersectPoint(set<PII> curlines,int k1,int b1){

  set<PDD> points;

  for(auto line:curlines){

    int k2=line.first,b2=line.second;

    if(k1!=k2){

      double x = (double)(b2 - b1) / (k1 - k2);

      //注意！！！右边要转变成double类型做计算 用(b2-b1)*1.0/(k1-k2)也行

      double y = k1 * x + b1;

      points.insert({x,y});

    }

  }

  return points.size();

}

int main()

{

  int n;cin>>n;

  int ans=1;

  while(n--){

    int k,b;

    cin>>k>>b;

    if(!lines.count({k,b})){

      ans++;

      ans+=IntersectPoint(lines,k,b);

      lines.insert({k,b});

    }

  }

  cout<<ans;

  return 0;

}

同类题型

视频讲解

⬅️ 第六届 c++ B组 省赛 🏠 00-刷题理模型 ➡️ 1、字符排序