#P4090. [Neerc2013]Easy Geometry

    ID: 3283 传统题 1000ms 128MiB 尝试: 6 已通过: 1 难度: 7 上传者: 标签>CF2300提高+/省选-三分法二分查找凸性/单峰性判定

[Neerc2013]Easy Geometry

题目描述

一句话题意:

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

输入格式

第一行是一个正整数 nn ,且 3≤n≤1000003\le n \le 100000 。

接下来 nn 行,每行两个整数 xx , yy ,代表一个顶点的 xx 坐标和 yy 坐标。 −109≤x,y≤109-10^9 \le x,y \le 10^9 。

输出格式

输出四个整数 xmin,ymin,xmax,ymaxx_{min},y_{min},x_{max},y_{max} ,代表你给出的这个面积最大的矩形。其中 xmin≤xmaxx_{min} \le x_{max} , ymin≤ymaxy_{min} \le y_{max} 。

精度要求:如果 AA 是你算出的值, A′A' 是真实的最大面积,那么你需要保证 min(∣A−A′∣,∣A−A′∣/A′)≤10−5min( |A-A'|,|A-A'|/A') \le10^{-5} 。

输入输出样例 #1

输入 #1

4
5 1
2 4
3 7
7 3

输出 #1

3.5 2.5 5.5 4.5

输入输出样例 #2

输入 #2

5
1 1
1 4
4 7
7 4
7 1

输出 #2

1 1 7 4