UVALive - 4356 Fire-Control System

题意：在平面上有n个点，求一个圆心在原点的扇型，至少有k个点在里面，要求扇型面积尽量小

思路：首先先枚举半径，然后找到半径小于等于枚举值的点，其中要求点要连续，按正弦值的从小到大排序，因为我们要包括从大到小的连续查找，所以我们开一个两倍的储存数组，然后从我们找到的符合要求的点中，求出最小的扇型面积，注意当大于n的时候需要加一个圆的面积了，还有就是精度的问题，看了别人的才注意过来

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <cstring>
using namespace std;
const int MAXN = 5010;
const double eps = 1e-6;
const double pi = acos(-1.0);

int dcmp(double x){
    if (fabs(x) < eps)
        return 0;
    else return x < 0 ? -1 : 1;
}

struct node{
    int x,y;
    double ang;
    double len;
    node(int x = 0,int y = 0):x(x),y(y){
        ang = atan2(y,x);
        len = sqrt(x*x+y*y);
    }
    bool operator<(const node &t)const {
        return dcmp(ang-t.ang) < 0;
    }
}p[2*MAXN];
int n,k,a[2*MAXN];

int main(){
    int cas = 1;
    while (scanf("%d%d",&n,&k) != EOF && n+k){
        for (int i = 0; i < n; i++){
            int x,y;
            scanf("%d%d",&x,&y);
            p[i] = node(x,y);
        }
        sort(p,p+n);
        for (int i = n; i < 2*n; i++)
            p[i] = p[i-n];
        double ans = 1e10;
        for (int i = 0; i < n; i++){
            double r = p[i].len;
            int m = 0;
            for (int j = 0; j < 2*n; j++)
                if (dcmp(p[j].len-r) <= 0)
                    a[m++] = j;
            for (int j = 0; j < m-k+1; j++){
                if (a[j+k-1]-a[j] >= n || a[j] >= n)
                    break;
                double angle = p[a[j+k-1]].ang - p[a[j]].ang;
                if (a[j+k-1] >= n)
                    angle += 2*pi;
                ans = min(ans,r*r*angle/2);
            }
        }
        printf("Case #%d: %.2f\n",cas++,ans);
    }
    return 0;
}

UVALive - 4356 Fire-Control System

原文：http://blog.csdn.net/u011345136/article/details/18679453