快速放大三角形：求包含原三角形的最小整坐标三角形

嘿，咱们来一步步拆解怎么搞定这个问题——你说的“放大”我分两种最常见的场景来解释，毕竟不同的“放大”定义解法差不少：

场景1：DEF和ABC必须是相似放大（保持形状不变） #

如果要求DEF是ABC的相似放大版，同时是整数坐标（格点）三角形、完全包含ABC且面积最小，那核心思路围绕「相似比的合理性」和「格点坐标约束」展开：

关键前提 #

格点三角形的面积要么是整数，要么是半整数（根据皮克定理：面积 = 内部格点数 + 边上格点数/2 - 1），所以相似比的平方必须是有理数，也就是说相似比k本身得是有理数（比如整数、分数）。

具体步骤 #

• 优先尝试整数相似比：这是最直接的情况。比如取k=2，把ABC的每个顶点坐标直接乘以2，得到的DEF就是格点三角形，而且肯定包含原ABC。如果k=1的话，DEF就是ABC自己，但如果题目要求“严格放大”（ABC完全在DEF内部，不在边界上），那k得取大于1的最小整数，同时可以微调平移量让ABC完全落在DEF内部。
• 考虑分数相似比（仅当原三角形坐标有公约数时）：比如ABC的顶点是(2,0),(4,2),(6,0)，所有坐标都是2的倍数，那取k=3/2的话，把每个坐标乘以3再除以2，得到(3,0),(6,3),(9,0)，也是格点三角形，面积是原三角形的9/4倍，比k=2的面积（4倍原面积）更小。
• 验证严格包含：如果需要ABC完全在DEF内部，不能落在边界上，那找到合适的相似比后，给DEF的顶点做微小的整数平移（比如每个顶点都往远离ABC的方向移1个单位），确保ABC的所有点都在DEF内部。

场景2：DEF可以和ABC形状不同（仅要求包含且面积最小） #

如果“放大”只是广义的“包含”，不要求形状一致，那解法更简单：

• 非退化ABC（三点不共线）：最小的DEF就是ABC自己！因为ABC本身就是整数坐标三角形，而且没有比它面积更小的三角形能包含它了。
• 退化ABC（三点共线）：这时候ABC是一条线段，我们需要找这条线段距离最近的格点（不在线段所在直线上），这个格点和线段的两个端点组成的三角形就是面积最小的DEF。比如线段是(0,0),(3,0)，最近的格点是(0,1)，DEF就是(0,0),(3,0),(0,1)，面积1.5，是最小的可能。

举个实际例子 #

假设ABC的顶点是(0,1),(2,2),(1,0)：

• 如果要相似放大，最小的整数相似比是2，DEF的顶点是(0,2),(4,4),(2,0)，面积是原ABC的4倍，完全包含原三角形；
• 如果不要求相似，那DEF就是ABC自己，用坐标公式计算面积为1.5，是能包含它的最小面积格点三角形。

内容的提问来源于stack exchange，提问作者VanDir