题目详情题解（0）讨论（0）提交记录（0）

AT_abc075_d.[ABC075D] Axis-Parallel Rectangle

提高+/省选-

通过率：0%

AC君温馨提醒

该题目为【atcoder】题库的题目，您提交的代码将被提交至atcoder进行远程评测，并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供，我们无法保证该服务的稳定性，若提交后无反应，请等待一段时间后再进行重试。

题目描述

在二维坐标系上有 NN 个点。
第 ii 个点的坐标为 (xi,yi)(x_i, y_i)。
请考虑所有边平行于 XX 轴或 YY 轴的矩形，这些矩形内部（包括边界）至少包含 KK 个点。
在所有满足条件的矩形中，求面积最小的那个矩形的面积。

输入格式

输入以如下格式从标准输入读入。

NN KK
x1x_1 y1y_1
x2x_2 y2y_2
⋮\vdots
xNx_N yNy_N

输出格式

请输出满足条件的矩形中面积最小的那个矩形的面积。

输入输出样例

  • 输入#1

    4 4
1 4
3 3
6 2
8 1

    输出#1

    21

  • 输入#2

    4 2
0 0
1 1
2 2
3 3

    输出#2

    1

  • 输入#3

    4 3
-1000000000 -1000000000
1000000000 1000000000
-999999999 999999999
999999999 -999999999

    输出#3

    3999999996000000001

说明/提示

限制条件

  • 2≤K≤N≤502 \leq K \leq N \leq 50
  • −109≤xi,yi≤109 (1≤i≤N)-10^9 \leq x_i, y_i \leq 10^9\ (1 \leq i \leq N)
  • xi≠xj (1≤i<j≤N)x_i \neq x_j\ (1 \leq i < j \leq N)
  • yi≠yj (1≤i<j≤N)y_i \neq y_j\ (1 \leq i < j \leq N)
  • 所有输入值均为整数。（21:50 补充）

样例解释 1

满足条件且面积最小的矩形之一由 (1,1),(8,1),(1,4),(8,4)(1,1),(8,1),(1,4),(8,4) 这四个顶点构成。其面积为 (8−1)×(4−1)=21(8-1) \times (4-1) = 21，因此输出 2121。

样例解释 3

请注意防止溢出。

由 ChatGPT 4.1 翻译

输入解题思路，AI测评打分。不知道怎么写?

首页