# 山东省第六届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

2
1 1
1 1
2 2
1 1
1 2


## Example Output

1
2


## AC 代码

#include<bits/stdc++.h>
using namespace std;
#define LL long long
#define INF 0x3f3f3f

const 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<n; i++)
{
int x,y;
scanf("%d %d",&x,&y);
arr[x][y]=1;
}
for(int i=0; i<=n; i++)
for(int j=0; j<=n; j++) // 向右推进
arr[i][j] += arr[i][j-1];
for(int i=0; i<=n; i++)
for(int j=0; j<=n; j++) // 向下推进
arr[i][j] += arr[i-1][j];
int ans = n*n;
for(int i=0; i<=n; i++) // 枚举两行
for(int j=i+1; j<=n; j++)
ans = min(ans,(j-i)*cal(arr[i],arr[j],k));
printf("%d\n",ans);
}
return 0;
}