Wireless Signal

A house will have maximum signal strength if the signal doesn’t have to travel through another house, that is, if we draw a straight line from the town hall to that house, the line doesn’t go through another line. Now let the coordinate of the town-hall be $(x,y)$ and the coordinate of the candidate house be $(x_1,y_1)$, then $dx=abs(x-x_1)$ and $dy=abs(y-y_1)$, the house will have maximum signal iff $GCD(dx,dy)==1$, here GCD represents the greatest common divisor of two numbers.

Using inclusion-exclusion and bit-masking we can calculate the number of coordinates with $GCD(dx,dy)>1$ in $O(n*log(n) )$and using that we can find the other coordinates.