题解：P7661 [COCI2014-2015#5] TRAKTOR

· · 题解

题意

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

做法

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

我们就可以定义四个桶数组来记录每一条直线上点的个数，直到出现一个 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;//没找到
}