### PROBLEM LINK:

**Editorialist:** Jingbo Shang

### DIFFICULTY:

Hard

### PREREQUISITES:

Voronoi Diagram

### PROBLEM:

Given **N** points, find the area of the maximum empty circumcircle of an acute-angled triangle (3 corners are from **N** points).

### EXPLANATION:

First of all, I think this problem is a classical problem and then I search online. I find that it is called Largest Empty Circle. From wikipedia, we know that it is related to Voronoi Diagram and solvable in O(**NlogN**).

To calculate the Voronoi Diagram (VD) in O(**NlogN**) time, we can use Fortune’s algorithm (These **N** points are equivalent to the sites in Fortune’s algorithm). After that, let’s store the O(**N**) vertices of VD in a list **V**. For each vertex **v**, store also the following info:

- sites nearest to
**v**(these sites lie on the largest empty circle centered at**v**). - distance
**d**of the sites nearest to_{v}**v**.

All these info are obtained and stored during the circle event corresponding to **v**.

Then, we sort **V** in non-increasing order of **d _{v}** and check these vertices in order. For a given vertex

**v**, consider every three nearest sites (only a small constant number of nearest sites it may have) of

**v**to decide whether it forms an acute-angled triangle. If yes, return the area of the circle centered at

**v**and of radius

**d**. Otherwise, take the next vertex into consideration. This procedure also needs O(

_{v}**NlogN**) time.