How to solve this problem?

Revision en1, by aditya_sheth, 2020-05-24 09:45:13

There are two integer points A and B in the 2-D plane. We need to find another point C satisfying the following conditions:

  1. C has to be different from A and B.

  2. There is no integer coordinate point on the line segment AC other than its endpoints.

  3. There is no integer coordinate point on the line segment BC other than its endpoints.

  4. Triangle ABC must have a positive area.

  5. 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

Tags #number theory, #geometry

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en1 English aditya_sheth 2020-05-24 09:45:13 681 Initial revision (published)