牛客多校第六场 I 题题解

I Line

题意：给定大小为 $nn$ 的向量集 $S_{v}S\_v$，构造一个整点集 $S_{p}S\_p$ 使得 $\mathrm{\forall }P\in S_p\backslash forall\; P\backslash in\; S\_p$，$\mathrm{\forall }\vec{l}\in S_v\backslash forall\; \backslash vec\{l\}\; \backslash in\; S\_v$，直线 $(P,\vec{l})(P,\backslash vec\; l)$ 恰好经过 $S_{p}S\_p$ 中的 $dd$ 个点。$n,d\le 6n,d\; \backslash leq\; 6$，向量集中横纵坐标均为 $[0,6][0,6]$ 的整数。

解法：首先观察 $n=2n=2$ 的情况，取 $d=3d=3$：

当 $n=3n=3$ 时，可以看到其本质为将 $n=2n=2$ 的图形向新加入的向量 $\overrightarrow{l_3}\backslash vec\{l\_3\}$ 方向进行了平移。

因而做法即是，枚举每个向量，然后将已有的点向该方向进行平移。为了不让超过 $dd$ 个点共线，因而每次平移的距离需要是上一次的倍数，使得上一次的图形不会和这一次的发生重叠。本题可以取 $2323$ 倍。

#include <bits/stdc++.h>
using namespace std;
int th[10];
int main()
{
    th[0] = 1;
    for (int i = 1; i < 10;i++)
        th[i] = th[i - 1] * 23;
    int n, d;
    scanf("%d%d", &n, &d);
    set<pair<int, int>> s, ans;
    for (int i = 1, x, y; i <= n;i++)
    {
        scanf("%d%d", &x, &y);
        int d = __gcd(x, y);
        s.insert(make_pair(x / d, y / d));
    }
    ans.insert(make_pair(0, 0));
    int id = -1;
    for (auto dir : s)
    {
        id++;
        auto t = ans;
        for (auto i : t)
            for (int j = 1; j < d;j++)
                ans.insert(make_pair(i.first + j * dir.first * th[id], i.second + j * dir.second * th[id]));
    }
    printf("%d\n", ans.size());
    for(auto i:ans)
        printf("%d %d\n", i.first, i.second);
    return 0;
}