#PPCQ3. PPCQ 的数学题

PPCQ 的数学题

题目背景

有这么一道题:

给出三点坐标,求围成三角形面积。

PPCQ 想,这不就是 “海伦 - 秦九韶公式” 嘛,于是就愉快地做了。但是,看到别人代码都很短,是一个叫做「鞋带公式」的东西(大概是按照题意写的)。PPCQ 直接急哭了。。。

「鞋带公式」:$2S=|x_1(y_2 - y_3) + x_2(y_3 - y_1) + x_3(y_1 - y_2)|$,(x1,y1),(x2,y2),(x3,y3)(x_1,y_1),(x_2,y_2),(x_3,y_3) 分别是三角形三个点的坐标。

题目描述

PPCQ 有一个平面。这个平面上有 nn 个点,第 ii 个点的坐标为 (xi,yi)(x_i, y_i)。要知道,平面内三个不共线的点可以组成三角形。但是这样的三角形太多了,PPCQ 不喜欢这么多普通的三角形,于是定义了一个 good 三角形:边长不超过 kk 的三角形。这样就好多了。

但是这样的 good 三角形还是很多,于是想请教你:这些 good 三角形中,面积最大的三角形的面积是多大?

输入输出

输入共 n+1n+1 行。

  • 第一行有两个整数:n,kn, k,分别表示平面内有多少个点、good 三角形的最大边长。
  • 接下来 nn 行,第 ii 行有两个整数 xi,yix_i,y_i,表示第 ii 个点的坐标。

输出共 11 行,一个实数。表示面积最大的 good 三角形的面积,保留 11 位小数。

样例

3 10
2 2 
2 6 
7 2
10.0

说明:只有 11 个三角形,且是一个 good 三角形,所以答案为这个三角形的面积。

数据范围

  • 对于 20%20\% 的数据:n<100,k<10n<100,k<10
  • 对于 50%50\% 的数据:n<1000,k<109n<1000,k<10^9
  • 对于 100%100\% 的数据:n<105,k<109n<10^5,k<10^91xi,yi1051\le x_i,y_i\le 10^5