题目描述

Eva studies geometry. The current topic is about convex polygons, but Eva prefers rectangles. Eva's workbook contains drawings of several convex polygons and she is curious what is the area of the maximum rectangle that fits inside each of them.

Help Eva! Given the convex polygon, find the rectangle of the maximum possible area that fits inside this polygon. Sides of the rectangle must be parallel to the coordinate axes.

输入格式

The first line contains a single integer $n$ -- the number of sides of the polygon $(3 \le n \le 100 000)$ . The following $n$ lines contain Cartesian coordinates of the polygon's vertices -- two integers $x_{i}$ and $y_{i} (-10^{9} \le x_{i}, y_{i} \le 10^{9})$ per line. Vertices are given in the clockwise order.

The polygon is convex.

输出格式

Output four real numbers $x_{mi_n}, y_{mi_n}, x_{max}$ and $y_{max}$ -- the coordinates of two rectangle's corners $(x_{mi_n} < x_{max}, y_{mi_n} < y_{max}).$ The rectangle must fit into the polygon and have the maximum possible area.

The absolute precision of the coordinates should be at least $10-^{5}.$

The absolute or relative precision of the rectangle area should be at least $10^{-5}.$ That is, if $A'$ ; is the actual maximum possible area, the following must hold: $mi_n(|A-A'|,|A−A'|/A') ) \le 10^{-5}.$

题目大意

一句话题意：

给你一个凸 $n$ 边形，并按顺时针给出每一个顶点的坐标，求出在这个凸 $n$ 边形之内的面积最大的一个边平行坐标轴的矩形的四个顶点。

输入格式：

第一行是一个正整数 $n$ ，且 $3\le n \le 100000$ 。

接下来 $n$ 行，每行两个整数 $x$ ， $y$ ，代表一个顶点的 $x$ 坐标和 $y$ 坐标。 $-10^9 \le x,y \le 10^9$ 。

输出格式：

输出四个整数 $x_{min},y_{min},x_{max},y_{max}$ ，代表你给出的这个面积最大的矩形。其中 $x_{min} \le x_{max}$ ， $y_{min} \le y_{max}$ 。

精度要求：如果 $A$ 是你算出的值， $A'$ 是真实的最大面积，那么你需要保证 $min( |A-A'|,|A-A'|/A') \le10^{-5}$ 。

4
5 1
2 4
3 7
7 3

3.5 2.5 5.5 4.5

5
1 1
1 4
4 7
7 4
7 1

1 1 7 4

提示

Time limit: 1 s, Memory limit: 128 MB.