This page is still under construction.

Parts of this page are still being built. What you see may change.

Physical Distancing

Interview

Time limit1sMemory limit256 MB

Summary
Given points in a rectangle, find the widest corridor you can walk through from one end to the other, keeping that distance from every point.
Level

Medium7 of 10

Topics
Geometry, Union-find, Binary search, Graph
Solved
No attempts yet

Problem

To prevent the spread of Covid-19, people are asked to keep their distance from other people, who could be infected. Some experts recommend a distance of 2 metres, others 6 feet, and still others 1.5 metres. In some crowded settings, these recommended distances may not be possible. In any setting, maximizing the distance minimizes the risk of getting infected.

You need to walk down a crowded hallway in which other people are standing. Determine the maximum possible distance that you can maintain from all the other people while still being able to navigate from one end of the hallway to the other. (Assume that you and every other person is a point with zero area.)

Input

The first line contains three space-separated integers L, W, N, the length and width of the hallway and the number of people standing in it, with 0 < L, W ≤ 100 and 1 ≤ N ≤ 100. Each of these integers is between 0 and 100, inclusive. The following N lines each contain two integers X, Y, the coordinates of the location of each person, with 0 ≤ X ≤ L and 0 ≤ Y ≤ W.

Output

Output a single number, the maximum distance that you can maintain from any other person while navigating the length of the hallway. Your answer will be considered correct if the absolute or relative error to the judge's answer is within 10−4.

Examples2

  1. Example 1

    Input
    100 100 1
    50 50
    
    Expected output
    50.00000000000000
    
  2. Example 2

    Input
    100 2 2
    49 0
    51 2
    
    Expected output
    1.41421356237310