计算每条线段经过的整数点并用map判断

解题思路:

注意事项:

参考代码:

#include<bits/stdc++.h>
using namespace std;
typedef pair<int,int> PI;
map<PI,int>M; 
map<PI,bool>vis;
int gcd(int a,int b){
	if(b==0) return a;
	else return gcd(b,a%b);
}
int n;
int ans = 0;
int main(){
	cin >> n;
	for(int i = 1 ; i <= n ; i ++){
		int x1,y1,x2,y2;
		cin >> x1 >> y1 >> x2 >> y2;
		int g = gcd(abs(x1-x2),abs(y1-y2));
		int ax = (x2-x1)/g;
		int ay = (y2-y1)/g;
		while(x1 != x2 || y1 != y2){
			M[PI(x1,y1)]++;
			if(M[PI(x1,y1)] >= 2 && !vis[PI(x1,y1)]){
				ans ++;
				vis[PI(x1,y1)] = 1;
			}
			x1 += ax;
			y1 += ay;
		}
		M[{x2,y2}]++;
		if(M[PI(x2,y2)] >= 2&& !vis[PI(x2,y2)]){
			ans ++;
			vis[PI(x2,y2)] = 1;
		}
	}

	cout << ans <<endl;
	return 0; 
}