Practice on Toph

Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

Reconstruction of Durbar Bangla

Limits: 1s, 512 MB

KUET has a liberation war sculpture. The name of the sculpture is Durbar Bangla. This is the heart of KUET campus. The sculpture has a circular base and it is situated in an almost square shaped field.

Let’s say, the sculpture needs to be reconstructed. We have a square field, in which the sculpture will be placed. But there is a restriction of doing the reconstruction. The field has some special points. The center of the circular base of the sculpture needs to be coincide with any of these points.

For simplicity, assume the square field is axis parallel. You are given the lower left and upper right coordinates of the square field. Also you are given N special points. Your task is to reconstruct the Durbar Bangla whose base area is maximum possible and fits within the square field.

Can you do this?


The first line of the input contains four integers xa ya xb yb.

(xa, ya) point is the lower left corner and (xb, yb) point is the upper right corner of the square.

The second line contains an integer N. Which is the number of special points.

Each of the next N lines will contain the special coordinates.


  • 1 ≤ N ≤ 105
  • xa ≤ xb
  • ya ≤ yb
  • 1 ≤ xa, ya, xb, yb ≤ 1000
  • It is guaranteed that all the given special points are within the square
  • pi = 3.141593


Print the maximum area of the base of Durbar Bangla after reconstruction. Your answer will be considered correct if its relative or absolute error doesn’t exceed 10-6.


1 1 5 5
3 3
4 2
4 5


For example, C1 and C2 are two special points. If we take C2 we can build the largest circular base.

For your observation,

This is Durbar Bangla


Login to submit