Posted on 2010-08-18 16:44
acronix 阅读(167)
评论(0) 编辑 收藏 引用 所属分类:
hzshuai解题报告
题意:找最小角中的最大角,具体见题分析:纯枚举A选的点,计算此点能得到的最小角,枚举完后取最大。
主要用到atan2(y,x)求(0,0)与(x,y)的连线与0-x轴的弧度[-PI , PI].
PI = acos(-1.0). cpp代码:
#include <cstdio>
#include <cmath>
#include <algorithm>
using namespace std;
const double PI = acos(-1.0);
double x[1010],y[1010],MAX,MIN;
double d[1010];
int n;
inline double myatan2(double y,double x)
{
double t = atan2(y,x);
// printf("%lf\n",t >= 0 ? t : t + 2*PI);
return t >= 0 ? t : t + 2*PI;
}
int main()
{
int i,j,k,cnt;
while (scanf("%d",&n) && n >= 3)
{
MAX = -1.0;
for (i = 1; i <= n; i++)
scanf("%lf %lf",&x[i],&y[i]);
for (i = 1; i <= n; i++)
{
MIN = PI;
cnt = 0;
for (j = 1; j <= n; j ++)
if (j != i)
d[++cnt] = myatan2(y[j]-y[i],x[j]-x[i]);
sort(d+1,d+cnt+1);
for (k = 2; k <= cnt; k++)
if (MIN > d[k]-d[k-1])
{
MIN = d[k] - d[k-1];
}
double temp = (2*PI - (d[cnt] - d[1]));
if (MIN > temp)
{
MIN = temp;
}
if (MIN > MAX)
MAX = MIN;
}
printf("%.4lf\n",(MAX*180)/PI);
}
return 0;
}