#include <cstdio>
#include <cmath>
#include <algorithm>
using namespace std;
const int SIZE = 5010;
const double PI = acos(-1.0);
const double PI2 = PI * 2;
// 保存每一个点
struct Point
{
    // 计算到原点的距离
    void CalDist(int x, int y)
    {
        dist = sqrt(double(x * x + y * y));
    }
    // 计算与 x 轴正方向的夹角
    void CalThet(int x, int y)
    {
        thet = acos((double)x / dist);
        if (y < 0)
            thet = PI2 - thet;
    }
    // 与 x 轴正方向的夹角，到原点的距离
    double thet, dist;
}pnt[SIZE * 3];
int n, n2, n3;
int k;
// 存储 k*2-1 个备选点
int candi[SIZE * 2];
bool Cmp(Point a, Point b)
{
    if (a.thet == b.thet)
        return a.dist > b.dist;
    return a.thet < b.thet;
}
void Solve()
{
    // 如果直接可以判定出来
    if (k <= 1) {
        puts("0.00");
        // 跳过输入数据
        while (n--)
            scanf("%*d%*d");
        return;
    }
    int i, j;
    int x, y;
    // 读入数据，并计算距离和夹角
    for (i = 0; i < n; ++i) {
        scanf("%d%d", &x, &y);
        pnt[i].CalDist(x, y);
        pnt[i].CalThet(x, y);
    }
    // 按照夹角排序
    sort(pnt, pnt + n, Cmp);
    // n 的 2 倍
    n2 = n << 1;
    // n 的 3 倍
    n3 = n2 + n;
    // 为了便于处理，在原来的数据左侧和右侧各放 n 个排好序的数据，只是角度有所变动
    memcpy(pnt + n, pnt, n * sizeof(Point));
    for (i = n; i < n2; ++i)
        pnt[i].thet += PI2;
    memcpy(pnt + n2, pnt + n, n * sizeof(Point));
    for (i = n2; i < n3; ++i)
        pnt[i].thet += PI2;
    int l, r;
    int lLmt, rLmt;
    int distMid;
    int distMid_sqr;
    int noLonger;
    int k_;
    double area;
    double minArea = 1e20;
    // 枚举一个点，取其到原点的距离作为此次枚举出的扇形的半径，从其两边各选取 k-1 个到原点不大于其距离的点
    for (i = n; i < n2; ++i) {
        distMid = pnt[i].dist;
        distMid_sqr = distMid * distMid;

        // 选取左边的 k-1 个点
        k_ = k;
        // 下标的下界
        lLmt = i - n;
        // 记录已有点的个数
        noLonger = 1;
        for (l = i - 1; l > lLmt && noLonger != k; --l) {
            // 找到了这样的一个点
            if (pnt[l].dist <= distMid) {
                ++noLonger;
                candi[--k_] = l;
            }
            // 找够 k 个，则退出
            if (noLonger == k)
                break;
        }
        if (noLonger != k)
            continue;

        candi[k] = i;

        // 选取左边的 k-1 个点
        k_ = k;
        // 下标的上界
        rLmt = i + n;
        // 记录已有点的个数
        noLonger = 1;
        for (r = i + 1; r < rLmt && noLonger != k; ++r) {
            // 找到了这样的一个点
            if (pnt[r].dist <= distMid) {
                ++noLonger;
                candi[++k_] = r;
            }
            // 找够 k 个，则退出
            if (noLonger == k)
                break;
        }
        // 枚举这 k 种可能，并更新最小值
        for (j = 1; j <= k; ++j) {
            area = distMid_sqr * (pnt[candi[j + k - 1]].thet - pnt[candi[j]].thet);
            if (minArea > area)
                minArea = area;
        }
    }
    printf("%.2lf\n", minArea / 2);
}
int main()
{
    int t;
    for (t = 1; scanf("%d%d", &n, &k) && (n || k); ++t) {
        printf("Case #%d: ", t);
        Solve();
    }
}

• 有没有人帮一下忙啊…… (0) lunch 2008-11-29 12:45:00