「AtCoder AGC036-A」Triangle

Description

给定一个正整数 $s$，找到三个格点 $(x_1,y_1),(x_2,y_2),(x_3,y_3)$，使它们围成的三角形面积为 $\frac{s}{2}$ 。可以证明一定有解。

$(1 \leq s \leq 10^{18},0 \leq x_1,y_1,x_2,y_2,x_3,y_3 \leq 10^9)$

Source

[AtCoder]AGC036-A

Solution

我们固定点 $(x_1,y_1)$ 为 $(0,0)$，显然这个点对三角形的面积没有影响，于是问题就变为寻找两个点。

而这两个点的向量叉积刚好等于 $\frac{s}{2} \times 2$，所以式子变为 $x_2y_3 - x_3y_2 = s$ 。

看上去还是不好求，为了包含所有解，不妨再设 $x_2 = 10^9,y_2 = 1$ 。

那么式子又变成了 $y_3 10^9 - x_3 = s$ 。

计算出 $s \bmod 10^9$ 就可以构造出 $(x_3,y_3)$ 了。

Code

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

template <class T>
inline void read(T &x) {
    x = 0;
    char c = getchar();
    bool f = 0;
    for (; !isdigit(c); c = getchar()) f ^= c == '-';
    for (; isdigit(c); c = getchar()) x = x * 10 + (c ^ 48);
    x = f ? -x : x;
}

template <class T>
inline void write(T x) {
    if (x < 0) {
        putchar('-');
        x = -x;
    }
    T y = 1;
    int len = 1;
    for (; y <= x / 10; y *= 10) ++len;
    for (; len; --len, x %= y, y /= 10) putchar(x / y + 48);
}

const int MAXN = 1e9;
LL s;

int main() {
    read(s);
    const int x1 = 0, y1 = 0, x2 = MAXN, y2 = 1;
    int x3 = MAXN - ((s - 1) % MAXN + 1), y3 = (s - 1) / MAXN + 1;
    write(x1);
    putchar(' ');
    write(y1);
    putchar(' ');
    write(x2);
    putchar(' ');
    write(y2);
    putchar(' ');
    write(x3);
    putchar(' ');
    write(y3);
    putchar('\n');
    return 0;
}