天梯赛2025 L2-054 三点共线 题解

题意简述

输入 n 个坐标其中 y 轴只能出现 {0,1,2} 三个值，x 轴数据范围为 [-1e6,1e6]。

你需要在这些点中寻找三点共线的点并按要求输出。

题解思路

其实我们可以通过数学推导可知，只需要计算斜率相同即可。可推出公式如下：

我们可以思考其实只需要枚举 y1 和 y0 随后查找 y2 是否存在就行。

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

const int N = 1e6 + 1000;
int y2[2 * N] = {0};

int main(){
	int n; cin >> n;
	vector<int> y0, y1;
	for(int i = 0;i < n;i ++){
		int x, y; cin >> x >> y;
		if(y == 0) y0.push_back(x);
		else if(y == 1) y1.push_back(x);
		else y2[x + N] = 1;
	}
	sort(y0.begin(),y0.end());
	y0.erase(unique(y0.begin(),y0.end()),y0.end());
	sort(y1.begin(),y1.end());
	y1.erase(unique(y1.begin(),y1.end()),y1.end());
	int f = -1;
	for(int j = 0;j < y1.size();j ++)
		for(int i = 0;i < y0.size();i ++){
            int num = 2 * y1[j] - y0[i];
			if(abs(num) <= 1e6 && y2[2 * y1[j] - y0[i] + N] == 1){
				cout << '[' << y0[i] << ", 0] " << '[' << y1[j] << ", 1] " << '[' << (2 * y1[j] - y0[i]) << ", 2]" << endl;
				f = 1;
			} 
		}
	if(f != 1) cout << f;
	return 0;
}

按照题目要求我们需要对原坐标点做排序去重处理，而且因为需要 y1 优先，所以外层循环必须为 y1 的循环。

我们在查找 y2 的时候无法使用哈希表，因为查找时间并不是完全的 O(1)。