自动搬运

查看原文

来自洛谷，原作者为

	Nt_Tsumiki 火星咖啡馆 || 我们终将相遇，在那悠远的苍穹 || xp是傲娇少女 || 绀海厨子捏 || 会不定时红温 || NOIP 2024 全国唯一一个 263 || 我是粘土投诉米奇

搬运于2025-08-24 22:31:57，当前版本为作者最后更新于2021-06-29 19:33:44，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

题意

在平面上有 $n$ 个点，每个店有自己的坐标 $x_i$ 和 $y_i$，现在给你一个数 $k$，求最小的 $i$ 使得前 $i$ 个数中有 $k$ 个数在同一直线上。

做法

根据题意我们知道，需要求在一个平面上点的个数，而在同一条直线上的点，有以下特征：

1. $x$ 一样
2. $y$ 一样
3. $x$ 与 $y$ 的和一样
4. $x$ 与 $y$ 的差一样

我们就可以定义四个桶数组来记录每一条直线上点的个数，直到出现一个 $i$ 让某一条直线满足要求（即点的个数等于 $k$），就输出，如果循环结束还没出现，就输出 $-1$，上代码。

Code

#include <iostream>

using namespace std;
int n,k;
int x,y;
int h[1000001],s[1000001],lx[2000001],rx[2000001];//桶数组，记录点数

int main() {
    cin>>n>>k;
    for (int i=1;i<=n;i++) {
        cin>>x>>y;
        h[y]++;
        s[x]++;
        lx[x+y]++;
        rx[x-y+1000000]++;
        if (h[y]==k or s[x]==k or lx[x+y]==k or rx[x-y+1000000]==k) { //满足要求
            cout<<i;
            return 0;
        }
    }
    cout<<-1;//没找到
}