题目描述

一句话题意：

给你一个凸 $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