题解 AT5144 【[AGC036A] Triangle】

· · 题解

题目大意

在一个 10^9\times10^9 的平面上,需要找到三个整点,使得三点构成的三角形的面积 =\frac{S}{2}.

分析

对于 S\leq 10^9 显然可以直接放在 \{(0,0),(s,0),(s,1)\},不多展开.

如果构造出来的三角形有一条边是与坐标平行的话显然 S 就必须要是这条边长度的位置,且这条边的长度必定是在 1 到 10^9 范围内的整数,显然是不能满足于所以的 S 的.所以需要换一种想法去构造.

使用与所有平面上的三角形的面积公式除了海伦公式,还会想到一个 \texttt{面积}=\frac{\texttt{水平宽}\times\texttt{铅垂高}}{2},在这里也就是 S= 水平宽\times 铅垂高,因为水平宽必定是整数,所以可以很自然地得出铅垂高 =\frac{S}{\texttt{水平宽}},将铅垂高的整数部分和小数部分分别表示为 a,b,也就是说 a=\lfloor\frac{S}{\texttt{水平宽}}\rfloor,因为 a 要在 1 到 10^9 的范围内,所以可以将水平宽取到 10^9,那么 b=\frac{S\bmod 10^9}{10^9},也就是需要构造出 1\times 10^{-9},2\times 10^{-9},3\times 10^{-9},\dots,(10^9-1)\times 10^{-9},那么也可以想到连接 (0,0) 与 (10^9,1) 的线段,在这条线段上恰好包含了上面所以的小数,而高度可以直接整除得到,于是可以构造出 \{(0,0),(10^9,1),(10^9-S\bmod 10^9,\lfloor\frac{S}{10^9}\rfloor+1)\}.(不理解可以画图理解).

以上做法在 S=10^{18} 的时候计算出来的高度大于了 10^9,所以需要特判这种情况.

代码

核心代码就三行,没啥必要了吧.