Help needed in a uva geometry problem

Revision en3, by t.muttaqueen, 2018-10-03 08:17:21

This a problem from UAP NCPC 2016. link: problem uva-13084

In short the description is:

A point in a n*n grid (n is maximum 5000) is considered troublesome if there exist another point in the grid which creates angle less than atan(1/k) and it is more than 0 degree where n^2<=k<=2n^2 with respect to the upper two corners. In the above picture C is a troublesome point. Output all the troublesome points in the grid. There are at most 10 test cases. No idea How to solve this problem. Any help?

Tags #geometry, #uva, #number theory

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en3 English t.muttaqueen 2018-10-03 08:17:21 47
en2 English t.muttaqueen 2018-10-03 08:16:30 29 Tiny change: 'atan(1/k) where n^2' -> 'atan(1/k) and it is more than 0 degree where n^2'
en1 English t.muttaqueen 2018-10-03 08:12:19 643 Initial revision (published)