山东省第六届 ACM 省赛 Stars （尺取法）

山东省第六届 ACM 省赛 Stars （尺取法）

Problem Description

There are N (1 ≤ N ≤ 400) stars in the sky. And each of them has a unique coordinate (x, y) (1 ≤ x, y ≤ N). Please calculate the minimum area of the rectangle (the edges of the rectangle must be parallel to the X, Y axes) that can cover at least K (1 ≤ K ≤ N) stars. The stars on the borders of the rectangle should not be counted, and the length of each rectangle’s edge should be an integer.

Input

Input may contain several test cases. The first line is a positive integer T (T ≤ 10), indicating the number of test cases below.For each test cases, the first line contains two integers N, K, indicating the total number of the stars and the number of stars the rectangle should cover at least.Each of the following N lines contains two integers x, y, indicating the coordinate of the stars.

Output

For each test case, output the answer on a single line.

Example Input

21 11 12 21 11 2

Example Output

12

题意

给出平面中 ​​n​​​ 个整数点，求最小的至少可以覆盖 ​​k​​ 个点的矩形面积。

思路

把这个平面看作一个矩阵，有整数点的位置为 ​​1​​​ ，其他位置为 ​​0​​ 。

求出 (1,1) 到任意点 (n,m)

AC 代码

#includeusing namespace std;#define LL long long#define INF 0x3f3f3fconst int maxn = 450;int arr[maxn][maxn];int v[maxn],n;int cal(int *l,int *r,int k){ int st,ed; st = ed = 0; for(int i=0; i<=n; i++) v[i] = r[i] - l[i]; while(ed <= n && v[ed] < k) ed++; if(ed > n)return INF; // 无法满足条件 int ret = ed; while(ed<=n) // 尺取法 { if(v[ed]-v[st] >= k) ret = min(ret,ed-st++); else ed++; } return ret;}int main(){ int T,k; scanf("%d",&T); while(T--) { scanf("%d %d",&n,&k); memset(arr,0,sizeof(arr)); for(int i=0; i

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。