Offer to come, dig friends take it! I am participating in the 2022 Spring Recruit Punch card activity. Click here for details.

I. Problem description

12. There are N straight lines in the plane. The ith straight line is y=Ai x+Bi.

Calculate how many parts these lines divide the plane.

Title link: Plane segmentation

Two, the title requirements

The sample

Input: 3 1 1 2 2 3 3 Output: 6Copy the code

inspection

1. Mathematical ideas 2. The recommended time is 20~35minCopy the code

Third, problem analysis

Suppose the question is changed to: How many regions can a plane be divided into for any n straight lines?

As shown in the figure above, the number of regions corresponding to the line is as follows:

11 2 4 3 7 4 11 5 16 6 22 7 29...... n n*(n+1)/2+1Copy the code

The number of regions on the NTH line is equal to the number of regions on the n-1st line plus the number of different intersections plus 1

For any n lines, the plane can be divided into at most n*(n+1)/2+1 blocks.

So if they give us a line, what do we do in different situations?

If the lines are parallel, the region is equal to n plus 1 and the lines overlap, and the region is equal to n plus 0 and the lines intersect, and the region is equal to the number of different points plus 1Copy the code

Four, coding implementation

#include<iostream>
#include<algorithm>
#include<math.h>
#include<set>
using namespace std;
typedef pair<double.double>line;
typedef long long ll;
set<line>l;
int check(double a1,double b1)
{
	set<line>p;
	double a3,b3;
	for(set<line>::iterator it=l.begin(a); it! =l.end(a); it++)// Remove existing advantages
	{
		double a2=it->first;
		double b2=it->second;
		if(a2! =a1)/ / not parallel
		{
			a3=(b1-b2)/(a2-a1);
			b3=a1*a3+b1;
			p.insert({a3,b3});// Insert intersections, judge the weight}}return p.size(a);// Returns the size
}
int main(a)
{
	ll i,n,ans=1;// Initialize the data
	cin>>n;// Enter the number of lines
	double x,y;// Line coordinates
	for(i=1; i<=n; i++) { cin>>x>>y;/ / input
		if(! l.count({x,y}))// Not a repeating line
		{
			l.insert({x,y});// insert set to assign weight
			ans+=check(x,y)+1;/ / intersection point
		}               
	}
	cout<<ans;// Return the result
	return 0;
}
Copy the code

Fifth, summary and improvement

1.Broken line

f(n)=f(n-1)+4*(n-1)+1

F (n) = 2 ∗ n2 – n + 12 * n ^ 2 – n + 12 ∗ n2 – n + 1

2.triangle

f(n)=f(n-1)+6*(n-1)+1


f ( n ) = 3 ∗ n ∗ ( n – 1 ) + 2 f(n)=3*n*(n-1)+2

3. The circular

f(n)=f(n-1)+2*(n-1)


f ( n ) = n 2 – n + 2 f(n)=n^2-n+2

4.Plane partition space

F (n) = 5 ∗ (n3 + n) / 6 + 1 (n ^ 3 + 5 * n) / 6 + 1 5 ∗ (n3 + n) / 6 + 1