自动搬运

查看原文

来自洛谷，原作者为

	Sweet_2013 今夕是何年？ | 234粉爆我妹的照片，求关 | 互关条件 /training/813543

搬运于2025-08-24 23:02:24，当前版本为作者最后更新于2024-12-29 01:22:55，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

暴力解法是：三层循环，遍历所有可能的点，每个点逐个判断是否有超过两个线段经过，然后记录个数。时间复杂度 $O(mx\times my\times n)$。

正解是这样的：

• 不再遍历所有可能点，而是遍历每条线段上的整数点。
• 将其出现的次数存到哈希表中。
• 遍历哈希表统计交点的数量。此时的时间复杂度最坏 $O(n\times \max(x,y))$。

#include<bits/stdc++.h>
using namespace std;
typedef pair<int, int> PII;
int n, m, ux[501], uy[501], vx[501], vy[501], ans;
map<PII, int> cnt_mp;
int gcd(int a, int b){return b?gcd(b,a%b):a;}
void count(int i){
    int x1=ux[i], x2=vx[i], y1=uy[i], y2=vy[i], dx=x2-x1, dy=y2-y1, d=gcd(abs(dx),abs(dy));
    dx/=d;
	dy/=d;
    for (int i=0; ;i++) {
        int x=x1+i*dx, y=y1+i*dy;
        cnt_mp[{x, y}]++;   
        if (x==x2&&y==y2) break;
    }
}
int main(){
	cin >> n;
    for (int i=0;i<n;i++) {
		cin >> ux[i]>> uy[i]>> vx[i]>> vy[i];
		count(i);
	}
    for (map<PII, int>::iterator it = cnt_mp.begin(); it != cnt_mp.end(); it++) if (it->second >= 2) ans++;
    cout <<ans<< endl;
	return 0;
}