You decide to benefit from the good weather by making a campsite with your friends. After a slow day of fishing, followed by a good meal around a wood fire during which you exhaust your entire repertoire of songs, you each lie back, relax and stare at the stars. Unfortunately you know very little about the constellations that you see.
For you, the stars do not form splendid creatures or characters, or even so much as a saucepan. You always found it absurd to memorise the names and positions of the different constellations – after all, by staring hard enough at several dots in space you can make them look like anything really. So you decide to seek out your own shapes in the stars.
To spice things up a little, you propose a small contest with your friends: the goal is to find the largest possible arrow in the night sky. There are no limits on what you can use, so while your friends are gazing upwards you secretly pull out your digital camera and laptop to guarantee victory.
You must write a program to find the largest possible arrow formed from precisely three stars. Your arrow must be pointing upwards1, and the two stars at the left and right sides of the arrow must be at precisely the same height. The star that forms the tip of the arrow must have its x-coordinate strictly between the other two, and its y-coordinate must be strictly above them.
Furthermore, the width of the arrow must be smaller or equal to its height. Note that the width of the arrow is defined to be the difference in x-coordinates between the leftmost star and the rightmost star, and the height of the arrow is defined to be the difference in y-coordinates between the tip of the arrow and the two stars beneath it.
Thus, if the three stars making up the arrow are at coordinates (x1,y1), (x2,y2) and (x3,y3), we must have x1 < x2 < x3 and y2 < y1 = y3. The width of the arrow is x3-x1 and the height of the arrow is y1-y2, and we must therefore also have x3-x1 <= y1-y2. The following diagrams illustrate several correct and incorrect arrows.
|Correct arrows||Incorrect arrows|
The size of an arrow is determined as its width plus its height. In seeking the largest arrow, you are therefore seeking the arrow whose width plus height is as large as possible.
Your program should read directly from standard input. The first line of input will contain a single integer: N, the number of visible stars in the sky (1 <= N <= 2000).
Following this will be N lines each describing a single star. Each of these lines will contain two positive integers separated by a space: the x and y coordinates of the star (0 <= x,y <= 1,000,000). You are guaranteed that no two stars will be at the same location in the sky.
Your program must write directly to standard output. Your output must consist of a single integer: the size of the largest arrow (i.e., its width plus its height). You are guaranteed that at least one correct arrow can be found.
The following input represents the night sky illustrated above, where the largest arrow is marked in the diagram. The three stars forming this arrow are at coordinates (7,19), (8,1) and (14,19). This arrow has width 14-7 = 7 and height 19-1 = 18, giving a total size of 7+18 = 25.
10 6 15 14 19 2 15 5 8 8 1 8 15 11 16 7 19 10 15 5 20
1 Of course, the French contestants will be searching for arrows pointing downwards.