This page is still under construction.

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

The Perfect Symmetry

Time limit1sMemory limit128 MB

Summary
Given a set of distinct integer points, decide whether it has a center of symmetry and, if so, print that center to one decimal place.
Level

Medium5 of 10

Topics
Hash map, Geometry, Sorting, Math
Solved
No attempts yet

Problem

During a summit, the representatives of NATO countries must be protected by many bodyguards. Each V.I.P. is accompanied by their own bodyguards and is also assigned other specialists, snipers, and so on. To keep the guards effective and the protected person as safe as possible, the bodyguards are spread out in many directions around that person.

The optimal arrangement is one in which the V.I.P. stands exactly at the center of symmetry of all the guards. Unfortunately, whenever the V.I.P. moves it is very hard to rearrange the bodyguards in real time.

So the procedure is reversed: the bodyguards take their positions first, and then it is up to the V.I.P. to find the correct spot at the center of symmetry. If the person stands anywhere else, their safety cannot be guaranteed.

Your task is to automate this. Given a set of NN points (the bodyguard positions), find its center of symmetry SS, the spot where the V.I.P. is relatively safe. A more formal description follows.

Take a point AA and a candidate center SS. A point A′A' is the image of AA with respect to the center SS if and only if SS is the midpoint of the segment joining AA and A′A'.

The image of a set of points XX with respect to SS is the set of the images of all its individual points. The set XX has a center of symmetry if there exists a point SS such that the image of XX with respect to SS equals XX itself.

Input

The input contains several assignments. Each assignment begins with a line containing one integer NN (1≤N≤200001 \le N \le 20000). It is followed by NN lines, each containing two integers XiX_i and YiY_i separated by a space, where −105≤Xi,Yi≤105-10^5 \le X_i, Y_i \le 10^5. These are the Cartesian coordinates of the ii-th point of the set.

Since no two bodyguards share a place, no point appears twice within one assignment. A bodyguard, however, may stand at the very same place as the V.I.P.

After the last assignment comes a line containing 00 instead of a point count; this line is not processed.

Output

For each assignment, print exactly one line.

If the set has a center of symmetry, print

V.I.P. should stay at (X,Y).

where X and Y are the Cartesian coordinates of the center, each rounded to exactly one digit after the decimal point.

If the set has no center of symmetry, print

This is a dangerous situation!

Examples3

  1. Example 1

    Input
    8
    1 10
    3 6
    6 8
    6 2
    3 -4
    1 0
    -2 -2
    -2 4
    4
    2 1
    4 1
    5 1
    6 1
    0
    
    Expected output
    V.I.P. should stay at (2.0,3.0).
    This is a dangerous situation!
    
  2. Example 2

    Input
    1
    5 -7
    0
    
    Expected output
    V.I.P. should stay at (5.0,-7.0).
    
  3. Example 3

    Input
    2
    0 0
    2 2
    0
    
    Expected output
    V.I.P. should stay at (1.0,1.0).