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

Topic describes

In a plane rectangular coordinate system, two points can define a straight line. If there are multiple points on a line, then any two of those points will determine the same line.

Given plane 2 x 3 {the hour (x, y) | 0 x or less < 2, 0 or less y < 3, Z ∈ x, y, Z ∈}, namely the abscissa is 0 to 1 (including 0 and 1) integers, ordinate is between 0 to 2 (including 0 and 2) between the integer point. These points define 11 different lines.

A given plane 20 x 21 hour {(x, y) | 0 x or less < 20, 0 or less y < 21, Z ∈ x, y Z ∈}, The point where the x-coordinate is an integer between 0 and 19 and the y-coordinate is an integer between 0 and 20. How many different lines are determined by these points?

Train of thought

Do algorithm problems, it is easy to take some detours that should not go, such as clearly is brainless traversal, but always want to dynamic planning. How do you determine the general direction of each problem? One general direction is — look at the amount of data. As shown in this problem, two points determine a straight line, and a total of 20∗21=42020*21=42020∗21=420 points, that is, approximately 4202420^24202 complexity, which is perfectly acceptable for traversal. So I decided to focus on violent traversal of all points.

But the whole point of this problem is to figure out if these two lines are the same. At first I was obsessed with drawing and finding patterns, always thinking there was an O(1) solution, but it turns out that some things have to be done by a clever computer

For a line formed by any two points, we just need to find its equation y=kx+by=kx+by=kx+ B of k and B, and then we can determine whether KKK and BBB are equal to each other. Of course, if KKK does not exist, simply add 20 to the result.

For (x1, x2), (y1, y2) (x_1, x_2), (y_1, y_2) (x1, x2), (y1, y2) two dots (x1 indicates x2x_1 \ not = x_2x1  = x2), set up the equation of the straight line y = kx + by + by = = kx kx + b, is calculated:

Since k is the division of two numbers, the accuracy problem will appear when solving the equality directly. So you want to reduce it to the simplest fraction and keep the numerator and denominator. The way you do that is you divide the numerator and denominator by the GCD of both of them. Here’s the simplest k function.

void computek(int &dx,int &dy){
	int tmp=gcd(dx,dy);
	dx=dx/tmp;
	dy=dy/tmp;
}
Copy the code

If k is equal, you just have to figure out whether the numerator and denominator are equal. The thing to note is that notation is a little bit extra.

If KKK is equal, judge whether BBB is equal. Two line b1 = – kx1 + y1, b2 = – kx2 + y2, b_1 = kx_1 + y_1, b_2 = kx_2 + y_2, b1 = – kx1 + y1, b2 = – kx2 + y2, If b1=b2b_1=b_2b1= B2, y2− Y1x2 −x1=k\frac{y2-y1}{x2-x_1}= Kx2 −x1y2−y1=k. The judgment function is as follows:

struct line{
	int kx,ky;
	bool fu;
	int x1,y1;
};
bool iseql(line &a,line &b){
	if(a.kx==b.kx&&a.ky==b.ky&&a.fu==b.fu){
		if(a.x1==b.x1&&a.y1==b.y1){
			return 1;
		}else{
			int dy=a.y1-b.y1;
			int dx=a.x1-b.x1;
			int fu=dx*dy<0;
			dy=abs(dy);
			dx=abs(dx);
			computek(dx,dy);
			if(dx==a.kx&&dy==a.ky&&fu==a.fu){
				return 1;
			}
		}
	}
	return 0;
}
Copy the code

All the major problems have been solved by now.

The complete code

#include<bits/stdc++.h> using namespace std; #define pb push_back #define pp pop_back using ll=long long; using db =double; int gcd(int a,int b){ if(a<b)return gcd(b,a); if(b==0)return a; return gcd(b,a%b); } void computek(int &dx,int &dy){ int tmp=gcd(dx,dy); dx=dx/tmp; dy=dy/tmp; } struct line{ int kx,ky; bool fu; int x1,y1; }; bool iseql(line &a,line &b){ if(a.kx==b.kx&&a.ky==b.ky&&a.fu==b.fu){ if(a.x1==b.x1&&a.y1==b.y1){ return 1; }else{ int dy=a.y1-b.y1; int dx=a.x1-b.x1; int fu=dx*dy<0; dy=abs(dy); dx=abs(dx); computek(dx,dy); if(dx==a.kx&&dy==a.ky&&fu==a.fu){ return 1; } } } return 0; } vector<line> lines; int main(){ for(int x1=0; x1<=19; x1++){ for(int y1=0; y1<=20; y1++){ for(int x2=0; x2<=19; x2++){ for(int y2=0; y2<=20; y2++){ int dy=y2-y1; int dx=x2-x1; if(dx==0)continue; int fu=dx*dy<0; dy=abs(dy); dx=abs(dx); computek(dx,dy); line a={dx,dy,fu,x1,y1}; int flag=1; for(auto b:lines){ if(iseql(a,b))flag=0; } if(flag)lines.pb(a); } } } } cout<<lines.size()+20; return 0; }Copy the code

conclusion

This is the first version of this problem, because it involves the plus and minus sign problem so write a little messy. – Next time we will release an iterative version that will run faster (this article code took me nearly half a minute to run)