2469.txt

求K个点副开的面呢! 求K个点副开的面呢! 求K个点副开的面呢!

#include<stdio.h>
#include<algorithm>
#include<math.h>
using namespace std;
const int M=5105;
const double PI=acos(-1.0);
const double INF=1E200;
typedef struct Point
{
    int x;
    int y;
    int r;
    double angle;
}Point;
Point p[M];
bool cmp(Point a,Point b)
{
    return a.angle<b.angle;
}
double Alpha(Point q)
{
    if(q.x>0&&q.y==0)
        return 0;
    if(q.x==0&&q.y>0)
        return PI/2;
    if(q.x<0&&q.y==0)
        return PI;
    if(q.x==0&&q.y<0)
        return PI*1.5;
    if(q.x>0&&q.y>0)
        return atan(q.y*1.0/q.x);
    if(q.x<0&&q.y>0)
        return PI-atan(q.y*1.0/-q.x);
    if(q.x<0&&q.y<0)
        return PI+atan(-q.y*1.0/-q.x);
    if(q.x>0&&q.y<0)
        return 2*PI-atan(-q.y*1.0/q.x);
	return 0;
}
int main()
{
    int n,k,i,j,maxR,count=1;
    double area,s;
    while(scanf("%d%d",&n,&k)&&(n||k))
    {
        for(i=1;i<=n;i++)
        {
            scanf("%d%d",&p[i].x,&p[i].y);
            p[i].r=p[i].x*p[i].x+p[i].y*p[i].y;
            p[i].angle=Alpha(p[i]);
        }
        if(k==1)
        {
            printf("Case #%d: 0.00\n",count++);
            continue;
        }
        sort(p+1,p+n+1,cmp);
        s=INF;
        for(i=1;i<=n-k+1;i++)
        {
            maxR=-1;
            for(j=i;j<=i+k-1;j++)
                if(p[j].r>maxR)
                    maxR=p[j].r;
            area=fabs((p[i+k-1].angle-p[i].angle))*maxR*0.5;
            if(area<s)
                s=area;
        }
        printf("Case #%d: %.2lf\n",count++,s);
    }
    return 0;
}
/*
3 1
0 1
1 0
-5 -6
3 2
0 2
2 0
-5 -6
0 0
 
Case #1: 0.00
Case #2: 3.14
*/


#include <math.h>
#include <stdio.h>
#include <stdlib.h>

#define sqr(x) ((x) * (x))
#define pi 3.1415926535897932384626433832795

struct point
{
    int x, y;
    double slope;
};

int cmp(const void *a, const void *b)
{
    point *c = (point *)a;
    point *d = (point *)b;
    if(c->slope < d->slope) return -1;
    return 1;
}

int cmpint(const void *a, const void *b)
{
    if(*(int *)a < *(int *)b) return -1;
    return 1;
}

int main()
{
    point p[5005];
    int r[5005], tr[5005], test = 1;
    int n, k, i, j, cnt, s, e;
    double min_angle, angle, area, min_area;
    while(scanf("%d%d", &n, &k) != EOF)
    {
        if(n == 0 && k == 0) break;
        for(i = 0;i < n;i++)
        {
            scanf("%d%d", &p[i].x, &p[i].y);
            p[i].slope = atan2(p[i].y, p[i].x);
            if(p[i].slope < 0) p[i].slope += 2 * pi;
        }
        qsort(p, n, sizeof(p[0]), cmp);
        for(i = 0;i < n;i++)
            r[i] = tr[i] =  sqr(p[i].x) + sqr(p[i].y);
        qsort(r, n, sizeof(r[0]), cmpint);
        int rn = 1;
        for(i = 1;i < n;i++)
            if(r[i] != r[rn - 1]) r[rn++] = r[i];
        min_area = 1e250;
        for(i = rn - 1;i >= 0;i--)
        {
            min_angle = 100;
            cnt = 0;
            for(j = 0;j < n;j++)
            {
                if(tr[j] <= r[i])
                {
                     if(cnt == 0) s = e = j;
                     cnt++;
                }
            }
            if(cnt < k) break;
            cnt = 1;
            while(e < n)
            {
                while(cnt < k) 
                {
                    s++;
                    if(tr[s % n] <= r[i]) cnt++;
                }
                if(s >= n) angle = 2 * pi - fabs(p[s % n].slope -  p[e].slope);
                else angle = p[s].slope - p[e].slope;
                if(angle < min_angle) min_angle = angle;
                cnt--;
                e++;
                while(tr[e] > r[i] && e < n) e++;  
            }
            area = min_angle * r[i] / 2;    
            if(area < min_area) min_area = area;
        }
        printf("Case #%d: %.2lf\n", test++, min_area);
    }
    return 0;
}