QOJ.ac

QOJ

Time Limit: 1 s Memory Limit: 2048 MB Total points: 100

#10546. Triangle

Statistics

有一个三角形,其三个顶点 $A$、$B$ 和 $C$ 的坐标均为整数。如果在三角形的每一条边上各选择一个坐标为整数的点,并将这些点连接起来,就会形成一个新的三角形。在创建新三角形时,不能选择原三角形的顶点作为新三角形的顶点。

根据所选点的位置不同,新创建的三角形面积可能会有大有小。

你需要编写一个程序,找出满足条件的新三角形中面积最大和最小的情况(如果存在的话)。

例如,如下图所示,如果给定三角形的三个顶点坐标分别为 $(4, 8)$、$(-8, -1)$ 和 $(7, -7)$,则图 L.1(a) 中所示的黄色三角形是满足条件的所有三角形中面积最大的,而图 L.1(b) 中所示的蓝色三角形是面积最小的。

图 L.1(a) 和图 L.1(b)

给定三角形的某条边上可能不存在坐标为整数的点,在这种情况下,你所寻找的三角形不存在。

保证输入的三个点不在同一直线上。

输入格式

程序从标准输入读取数据。输入包含一行,包含六个整数,分别是三角形三个顶点 $A = (A_x, A_y)$、$B = (B_x, B_y)$ 和 $C = (C_x, C_y)$ 的 $(x, y)$ 坐标,按 $A_x, A_y, B_x, B_y, C_x, C_y$ 的顺序给出。每个坐标值均为 $-10^9$ 到 $10^9$ 之间的整数。

输出格式

程序向标准输出写入数据。设面积最大的新三角形面积为 $S_{\max}$,面积最小的新三角形面积为 $S_{\min}$。如果能找到这样的三角形,请按顺序输出 $2S_{\max}$ 和 $2S_{\min}$,其中 $2S_{\max}$ 和 $2S_{\min}$ 均为正整数。如果找不到这样的三角形,请输出 -1。

样例

样例输入 1

4 8 -8 -1 7 -7

样例输出 1

69 46

样例输入 2

-8 1 7 11 7 -5

样例输出 2

121 23

样例输入 3

0 0 1 10 10 0

样例输出 3

-1

Discussions

About Discussions

The discussion section is only for posting: General Discussions (problem-solving strategies, alternative approaches), and Off-topic conversations.

This is NOT for reporting issues! If you want to report bugs or errors, please use the Issues section below.

Open Discussions 0
No discussions in this category.

Issues

About Issues

If you find any issues with the problem (statement, scoring, time/memory limits, test cases, etc.), you may submit an issue here. A problem moderator will review your issue.

Guidelines:

  1. This is not a place to publish discussions, editorials, or requests to debug your code. Issues are only visible to you and problem moderators.
  2. Do not submit duplicated issues.
  3. Issues must be filed in English or Chinese only.
Active Issues 0
No issues in this category.
Closed/Resolved Issues 0
No issues in this category.