LA 4356 Fire-Control System -

题目地址：http://vjudge.net/problem/UVALive-4356

肯定是暴力

暴力 先定半径，枚举点效率高点

点可以事先极角排序，就可以利用atan2算角度，atan2算的是与x正半轴的夹角(180，180]，排序后是顺时针的转，所以两个角度相减得到的是顺时针转的角度，当转过一圈，就要加2*PI

然后可以枚举半径，得到所有的小于R的点，枚举每个点出发，计算包含个点的扇形,,更新答案

#include <bits/stdc++.h>
using namespace std;
#define REP(i,a,b)  for(int i=a;i<=(int)(b);++i)
#define REPD(i,a,b) for(int i=a;i>=(int)(b);--i)
const int maxn=5000+5;
const double PI=atan2(0,-1);
struct Point
{int x,y,r;double ang;bool operator < (const Point& p) const{return ang<p.ang;}
}points[maxn];
double R[maxn];  double Angle[maxn];
int getR(int i){return points[i].x*points[i].x+points[i].y*points[i].y;
}
int main(int argc, char const *argv[])
{int n,k,kase=0;while(scanf("%d%d",&n,&k)==2&&n+k){int Rcnt=0;REP(i,0,n-1) {scanf("%d%d",&points[i].x,&points[i].y);R[Rcnt++]=getR(i); points[i].r=R[Rcnt-1]; points[i].ang=atan2((double)points[i].y,(double)points[i].x);}if(n==1) {printf("Case #%d: 0.00\n", ++kase);continue;}sort(points,points+n);sort(R,R+Rcnt);Rcnt=unique(R,R+Rcnt)-R;double ans=1e10;REP(t,0,Rcnt-1){int cnt=0; REP(j,0,n-1) if(R[t]>=points[j].r) Angle[cnt++]=points[j].ang;if(cnt<k) continue;int front=k-1,rear=0; double ang;while(rear<cnt){   //循环if(front<cnt) ang=Angle[front]-Angle[rear];else ang=Angle[front-cnt]-Angle[rear]+PI+PI;ans=min(ans,(double)R[t]*ang*0.5);rear++;front++;}}printf("Case #%d: %.2lf\n", ++kase,ans);}return 0;
}