There are two integer points A and B in the 2-D plane. We need to find another point C satisfying the following conditions:
C has to be different from A and B.
There is no integer coordinate point on the line segment AC other than its endpoints.
There is no integer coordinate point on the line segment BC other than its endpoints.
Triangle ABC must have a positive area.
There is no integer coordinate point strictly inside ABC.
Constraints:
1.|Ax| <= 1e9, |Ay| <= 1e9, |Bx| <= 1e9, |By| <= 1e9.
2.Cx and Cy must be within [-1e14, 1e14].
Problem link: problem D
This problem really asks you to use Pick's theorem, which just states that for a polygon with integer coordinates on the plane, its area equals $$$i + \frac{b}{2} - 1$$$ where $$$i$$$ is the number of integer points inside the polygon and $$$b$$$ is the number of integer points on its border.
Compute $$$p = 1 + \gcd(|A_x - B_x|, |A_y - B_y|)$$$, the number of points on the line from A to B, including endpoints. We want the triangle to have $$$i = 0, b = p + 1$$$, which means we want to have area $$$\frac{p-1}{2}$$$. But this also goes the other way; if our triangle has this area, since $$$b \geq p + 1$$$, we must have $$$i = 0, b = p + 1$$$. So we solve for its area now instead:
We want to satisfy: $$$|A_xB_y - A_yB_x + B_xC_y - B_yC_x + C_xA_y - C_yA_x| = p-1$$$, where the sign of the left term just depends on the orientation of the triangle. So we can try to solve it for both $$$p-1, -(p-1)$$$, without the absolute value. Either way, move the first two (constant) terms to the RHS, and reorder the LHS, we get: $$$(A_y - B_y) \cdot C_x + (B_x - A_x) \cdot C_y = D$$$ for some constant D. You can find whether this has 0 or infinite solutions, this is a standard equation ("extended gcd").