2024蓝桥杯C/C++ B组国赛
P10907 [蓝桥杯 2024 国 B] 蚂蚁开会 - 洛谷
暴力枚举：
把每条线段经过的整数点都求出，然后用map
如何求线段上的整点？
分别计算两点x轴坐标和y轴之差，取绝对值后，求出gcd，然后循环把整点为键，其值加一
最后从头到位遍历map，统计大于1的点有多少个
来看代码：
#include
#include
using namespace std;
int gcd(int a, int b)
{
if (b == 0)
{
return a;
}
else
{
return gcd(b, a % b);
}
}
map, int>arr;
vectorX1;
vectorY1;
vectorX2;
vectorY2;
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(n);
Y1 = vector(n);
X2 = vector(n);
Y2 = vector(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;
}
