一、问题描述
平面上有 N 条直线，其中第 i 条直线是 y=Ai⋅x+Bi。
请计算这些直线将平面分成了几个部分。
题目链接：平面切分
二、题目要求
样例
输入： 3 1 1 2 2 3 3 输出： 6
考察
数学思想 建议用时20~35min
三、问题分析
假如问题改成：任意n条直线，最多可以将平面分成多少块区域？
如上图所示，直线对应的区域数量如下所示：
1 1 2 4 3 7 4 11 5 16 6 22 7 29 ...... n n*(n+1)/2+1
第n条直线区域数目=第n-1条直线区域数目+不同交点数目+1
任意n条直线，最多可以将平面分成 n*(n+1)/2+1块区域。
那么题目给定直线，面对不同的情况如何判断？
直线平行，区域=n+1 直线重合，区域=n+0 直线相交，区域=不同交点数目+1
四、编码实现
usingnamespacestd; typedefpair<double,double>line; typedeflonglongll; set<line>l; intcheck(doublea1,doubleb1) { set<line>p; doublea3,b3; for(set<line>::iteratorit=l.begin();it!=l.end();it++)//取出已存在的优点 { doublea2=it->first; doubleb2=it->second; if(a2!=a1)//不平行 { a3=(b1-b2)/(a2-a1); b3=a1*a3+b1; p.insert({a3,b3});//交点插入，判重 } } returnp.size();//返回大小} intmain() { lli,n,ans=1;//初始化数据cin>>n;//输入直线数量doublex,y;//直线坐标for(i=1;i<=n;i++) { cin>>x>>y;//输入if(!l.count({x,y}))//不是重复的直线 { l.insert({x,y});//插入set判重ans+=check(x,y)+1;//求交点 } } cout<<ans;//返回结果return0; }
五、总结与提高
1.折线
f(n)=f(n-1)+4*(n-1)+1
f(n)=2∗n2−n+12*n^2-n+12∗n2−n+1
2.三角形
f(n)=f(n-1)+6*(n-1)+1
f(n)=3∗n∗(n−1)+2f(n)=3*n*(n-1)+2f(n)=3∗n∗(n−1)+2
3.圆形
f(n)=f(n-1)+2*(n-1)
f(n)=n2−n+2f(n)=n^2-n+2f(n)=n2−n+2
4.平面分割空间
f(n)=(n3+5∗n)/6+1(n^3+5*n)/6+1(n3+5∗n)/6+1
