nefu 635 Twinkle Twinkle Little Star

Twinkle Twinkle Little Star

Time Limit 2000ms Memory Limit 65536K

description

Twinkle, twinkle, little star, how I wonder what you are. Up above the world so high, like a diamond in the sky. Twinkle, twinkle, little star, how I wonder what you are. When the blazing sun is gone, when he nothing shines upon. The you show your little light, Twinkle, twinkle, little star Twinkle, twinkle, little star, How I wonder what you are. Twinkle, twinkle, little star, how I wonder what you are. ---- 　　Well, this song may take us back to our childhood. When we were young, we often looked up at the stars. How amazing they were! But, unfortunately, as we are becoming older and older, what used to be interesting can not interest us now. So what we can do is to find something more interesting! 　　Here is one, maybe. Assume that all the stars are so far from us that we can treat them as points in a plane. You are given N stars in the plane, and a number K (0≤K≤N). What you need to do is to find the minimum square covering at least K stars, whose edges are all parallel to the axis. The stars which are on the edges of the square are also covered.

input

The input will consist of multiple cases. Your program should process to the end of the input file.In the first line of one case, there are two integer N and K, 0 < N ≤ 1500, 0 ≤ K ≤ N. 　　The next N lines are the description of the stars, one star per line. The ith line consists of two integers Xi and Yi, |Xi| < 1000000, |Yi| < 1000000.

output

The output will consist of one line for each case, in the format of “Case X: Y”, while X is the case number counting from 1, and Y is the edge length of the minimum square. X and Y are all integers.

sample_input

4 4 0 0 0 1 1 0 2 2 4 2 0 0 1 1 2 2 3 3

sample_output

Case 1: 2 Case 2: 1

题意：有n个点，边平行于坐标轴的一个正方形至少覆盖k个点，求该正方形的最短边长是多少？

代码：

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#define N 1505
using namespace std;
struct node
{
 int x,y;
} digt[N];
int xx[N];
int yy[N];
int lx,ly;
int n,k;
int getx(int x)
{
   return int(lower_bound(xx,xx+lx,x)-xx);
}
int gety(int y)
{
    return int(lower_bound(yy,yy+ly,y)-yy);
}
int dp[N][N];
void init()
{
    memset(dp,0,sizeof(dp));
    for(int i=0; i<n; i++)
    {
        int x1=getx(digt[i].x);
        int y1=gety(digt[i].y);
        dp[x1][y1]++;
    }

    for(int i=1; i<ly; i++)
        dp[0][i]=dp[0][i-1]+dp[0][i];
    for(int i=1; i<lx; i++)
        dp[i][0]=dp[i-1][0]+dp[i][0];
    for(int i=1; i<lx; i++)
        for(int j=1; j<ly; j++)
            dp[i][j]=dp[i-1][j]+dp[i][j-1]-dp[i-1][j-1]+dp[i][j];
}
int nextx[N],nexty[N];
bool solve(int len)
{
    int t=0;
    for(int i=0;i<lx;i++)
    {
        for(;t<lx;t++)
            if(xx[i]+len<xx[t])break;

        nextx[i]=t-1;
    }
    t=0;
    for(int i=0;i<lx;i++)
    {
        for(;t<lx;t++)
            if(yy[i]+len<yy[t])break;
        nexty[i]=t-1;
    }

    int x1,y1;
    for(int i=0;i<lx;i++)
        for(int j=0;j<ly;j++)
        {
            x1=nextx[i];
            y1=nexty[j];

            int ll=0,rr=0,lr=0;
            if(i>0)ll=dp[i-1][y1];
            if(j>0)rr=dp[x1][j-1];
            if(i>0&&j>0)
                lr=dp[i-1][j-1];

            if(dp[x1][y1]-ll-rr+lr>=k)return true;

        }
    return false;
}
int main()
{
    int test=1;
    while(scanf("%d%d",&n,&k)!=EOF)
    {

        for(int i=0; i<n; i++)
        {
            scanf("%d%d",&digt[i].x,&digt[i].y);
            xx[i]=digt[i].x;
            yy[i]=digt[i].y;
        }
        sort(xx,xx+n);
        sort(yy,yy+n);
        lx=unique(xx,xx+n)-xx;
        ly=unique(yy,yy+n)-yy;
        init();
        int l=0,r=2000005;
        while(l<r)
        {
            int  mid=(l+r)>>1;
            if(solve(mid))r=mid;
            else l=mid+1;
        }
        printf("Case %d: %d\n",test++,l);
    }
    return 0;
}