2024蓝桥杯C/C++ B组国赛

P10907 [蓝桥杯 2024 国 B] 蚂蚁开会 – 洛谷

暴力枚举：

把每条线段经过的整数点都求出，然后用map<pair<int, int>, int> 来记录每条线段上的每个点，会被访问多少次

如何求线段上的整点？

分别计算两点x轴坐标和y轴之差，取绝对值后，求出gcd，然后循环把整点为键，其值加一

最后从头到位遍历map，统计大于1的点有多少个

来看代码：

#include <bits/stdc++.h>
#include<unordered_map>
using namespace std;

int gcd(int a, int b)
{
if (b == 0)
{
return a;
}
else
{
return gcd(b, a % b);
}
}

map<pair<int, int>, int>arr;
vector<int>X1;
vector<int>Y1;
vector<int>X2;
vector<int>Y2;
void find_points(int now)
{
int dx = X2[now] – X1[now];
int dy = Y2[now] – Y1[now];
int step = gcd(abs(dx), abs(dy));
if (step == 0)
{
arr[{dx, dy}]++;
}
dx /= step;
dy /= step;
for (int i = 0; i <= step; i++)
{
arr[{X1[now] + i * dx, Y1[now] + i * dy }]++;
}
}

int main()
{

int n;
cin >> n;
X1 = vector<int>(n);
Y1 = vector<int>(n);
X2 = vector<int>(n);
Y2 = vector<int>(n);
for (int i = 0; i < n; i++)
{
cin >> X1[i] >> Y1[i] >> X2[i] >> Y2[i];
}
//每条线段 都把整点求出
for (int i = 0; i < n; i++)
{
find_points(i);
}
int ans = 0;
for (auto &it : arr)
{
if (it.second > 1)
{
ans++;
}
}
cout << ans;

}