L2-054 三点共线

本题传送门

解题思路

本题思路是 确定前两个点，推出第三个点，由于我们要找目标在第三个集合中有没有，而这个数可能是负数，所以可以采取对v2所有数字映射为正整数，做个标记，后续查询时间复杂度为O(1)，然后把目标算出来之后也要映射一下，以对应v2，所以bool[tar+偏移量] 。

剪枝：由于v0,v1,v2经过了排序去重，所以算出目标值后，如果目标值小于v2中数的范围，由于tar会逐渐变小，如果小于范围，后续会变得更小，不可能出现结果了，直接break，如果大于范围，后续可能会变小到范围内，就continue。

运行结果：小于1000ms，题目要求是2000ms，完美完成任务

ac✅️代码

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;

const int OFFSET = 1e6;
bool exist[2000005];

void process(vector<int>& v)
{
	sort(v.begin() , v.end());
	v.erase(unique(v.begin(),v.end()) , v.end());
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	int n;cin>>n;
	vector<int> v0,v1,v2;
	for(int i = 0 ; i < n ; i++)
	{
		int x,y;
		cin>>x>>y;
		if(y == 0) v0.push_back(x);
		if(y == 1) v1.push_back(x);
		if(y == 2) v2.push_back(x);
		
	}
	
	process(v0);
	process(v1);
	process(v2);
	
	//将负数映射到整正数
	for(int x : v2) exist[x+OFFSET] = true;
	
	bool found = false;
	
	for(int x1 : v1)
	{
		for(int x0 : v0)
		{
			int tar = 2 * x1 - x0;//差值越来越大
			if(tar > 1e6) continue;
			if(tar < -1e6) break;
			if(exist[tar + OFFSET])
			{
				found = true;
				cout << "[" << x0 << ", 0] [" << x1 << ", 1] [" << tar << ", 2]\n";
			}
		}
	}
	
	if(!found) cout<<"-1"<<endl;
	return 0;
	
}