[Bluebridge cup 2020 preliminary] horizontal segmentation

subject

Title Description
There is... On the plane N A straight line , Among them the first i This straight line is y = Ai * x + Bi.
Please calculate these lines to divide the plane into several parts .
Input format
The first line contains an integer N.
following N That's ok , Each line contains two integers Ai, Bi.
about 50% The evaluation case of ,1 ≤ N ≤ 4, -10 ≤ Ai, Bi ≤ 10.
For all profiling use cases ,1 ≤ N ≤ 1000, -100000 ≤ Ai, Bi ≤ 100000.
Output format
An integer represents the answer .
sample input Copy
3
1 1
2 2
3 3
sample output Copy
6

analysis

First of all, we need to know a little common sense of Mathematics ： In the same plane , If you add a line , It does not intersect all lines in the plane , Then a plane will be added , If it intersects with a straight line in this plane and produces intersections at different positions , Then an additional plane will be added .
Then we are in the process of making questions , Just judge whether to repeat the edge , Calculate the number of different intersections between the newly added line and the previous line , The heavy side is very good judgment , Just mark it with an array , We can also use set（ It can automatically remove the weight ）.

Reference code

#include <iostream>
#include <cstdio>
#include <set>
#include <vector>
#include <cstring>
#include <cmath>
#include <queue>
#include <stack>
#include <algorithm>
#include <unordered_map>
#define LL long long
#define rep(i, a, b) for(int i = a; i <= b; i++)
#define reps(i, a, b) for(int i = a; i < b; i++) 
#define pre(i, a, b) for(int i = b; i >= a; i--)
using namespace std;

const int N = 1010;
typedef pair<double, double> PDD;

bool st[N]; // Used to mark heavy edges , Prevent double calculation of intersections 
double a[N][2];

int main()
{
    
	int n;
	cin >> n;
	
	int ans = 1; //  At the beginning, there is a plane 
	rep(i, 1, n)
	{
    
		cin >> a[i][0] >> a[i][1];
		set<PDD> point; //  Calculate the number of different intersections between the line and the line in the plane 
		
		rep(j, 1, i - 1)
		{
    
			if(st[j]) continue;
			if(a[i][0] == a[j][0])
			{
    
				if(a[i][1] == a[j][1]) 
				{
    
					st[i] = true;
					break;
				}
				
				else continue;
			}
			
			double x = (a[i][1] - a[j][1]) / (a[j][0] - a[i][0]);
			double y = a[i][0] * x + a[i][1];
			point.insert({
    x, y});
		}
		
		if(!st[i]) ans += point.size() + 1;
	}
	
	cout << ans << endl;
	return 0;
}