There is a house in New Orleans...
In fact, upon arriving in the city, the UTPC officers discover that there are many houses in New Orleans. But before even taking a single step, they are accosted by the mayor, who has heard of a certain geniosity among the group that can solve any problem. The problem he needs help with is thus:
The city of New Orleans can be represented as a 2D plane with $$$n$$$ houses located at different integer points along the plane. The city is planning on laying a new set of fiber-optic cables to service these houses, which will be built as a straight line on the plane. Because the mayor wants everyone to be close to the cable, he cares about the furthest distance that a house will be from the line of cable. There have been $$$q$$$ proposals for different lines, and so the mayor requests the assistance of the group to compute this value for each proposed line in order to figure out which plan is the best.
The group is eager to explore the rich history, live music, and famous cuisine of the city, so help them answer the mayor's queries as fast as possible so they can get back on track!
The first line of input contains two integers $$$n$$$ and $$$q$$$ ($$$1 \leq n,q \leq 2\cdot10^5$$$) — the number of houses and number of proposals.
The next $$$n$$$ lines contain two integers $$$x_i$$$ and $$$y_i$$$ ($$$|x_i|,|y_i| \leq 10^9$$$) — the coordinates of the $$$i$$$th house. It is guaranteed that no two houses share the same coordinates.
The next $$$q$$$ lines contain three integers $$$A_i, B_i, C_i$$$ ($$$|A_i|, |B_i|, |C_i|\leq 10^9$$$) — specifying the $$$i$$$th proposal is for a line with the equation $$$A_ix + B_iy + C_i = 0$$$. It is guaranteed that either $$$A_i$$$ or $$$B_i$$$ is nonzero.
For each proposal, output the furthest distance a house has from the line. Your answer will be considered correct if its absolute or relative error doesn't exceed $$$10^{-6}$$$.
2 20 01 1-1 1 01 1 -2
0.0000000000 1.4142135624
In the first test, there are houses at (0,0) and (1,1). The first proposal is the blue dotted line, which runs through both houses, so it has a maximum distance of 0 from any house. The second proposal is the green dotted line, and it is furthest from the house at (0,0), with a distance of sqrt(2).
