蓝桥杯 直线 map与vector的简单应用

蓝桥杯 直线 map与vector的简单应用

试题 C: 直线
10 分

在平面直角坐标系中，两点可以确定一条直线。如果有多点在一条直线上，
那么这些点中任意两点确定的直线是同一条。
给定平面上2 × 3个整点{(x, y)|0 ≤ x < 2, 0 ≤ y < 3, x ∈ Z, y ∈ Z}，即横坐标
是0到 1 (包含 0 和 1) 之间的整数、纵坐标是 0 到 2 (包含0和 2) 之间的整数
的点。这些点一共确定了 11 条不同的直线。
给定平面上 20× 21 个整点{(x, y)|0 ≤ x < 20, 0 ≤ y < 21, x ∈ Z, y ∈ Z}，即横
坐标是 0到 19 (包含 0 和 19) 之间的整数、纵坐标是 0 到 20(包含 0 和 20) 之
间的整数的点。请问这些点一共确定了多少条不同的直线。

结果:40257
————————————————
AC代码：

using namespace std;
#include
int main() {
	int cnt = 20 + 21;
	vector>vec;
	//存储坐标
	map, int>um;
	for (int i = 0; i <= 19; i++) {
		for (int j = 0; j <= 20; j++) {
			vec.emplace_back(i, j);
		}
	}
	for (int i = 0; i < vec.size(); i++) {
		for (int j = 0; j < vec.size(); j++) {
			if (vec[i].first == vec[j].first || vec[i].second == vec[j].second)continue;
			//求出直线的斜率 截距(求与x轴和y轴的截距都可以，不能用两个截距判断，参考过原点的情况)
			double k = (vec[j].second - vec[i].second) / (vec[j].first - vec[i].first);
			double tmp1 = (vec[i].second * vec[j].first - vec[i].first * vec[j].second) / (vec[j].first - vec[i].first);
			double tmp2 = (vec[i].first * vec[j].second - vec[i].second * vec[j].first) / (vec[j].second - vec[i].second);
			if (um[{tmp2, k}] == 0) {
				um[{tmp2, k}] = 1;
				cnt++;
			}
		}
	}
	cout << cnt << endl;
	return 0;
}