这篇博客是从旧博客 WordPress 迁移过来,内容可能存在转换异常。
传送门:http://acm.hdu.edu.cn/showproblem.php?pid=1077
很不错的一道题目。
方法是:数学+贪心+暴力
思路:
从所有点中依次取两点,然后判断到两点m, n距离为半径1的点centre(易知center在m, n连线的中垂线上)。然后判断其余有多少点在以centre为圆心的圆内,记作ans,最后找出最大的ans,就是要求的值。
不过代码不是很好理解,我作了图,把重要的地方用图来解释。
以下是AC代码:
// Author: Tanky Woo
// Blog: www.WuTianQi.com
#include
#include
using namespace std;
int nCases, nPoints;
typedef struct Point{
double x, y;
}Point;
Point point[305];
double dis(Point m, Point n)
{
Point p;
p.x = m.x - n.x;
p.y = m.y - n.y;
return p.x*p.x + p.y*p.y;
}
// 找出距离m, n两点长为1的点
// 也就是两点连线中垂线上的一点。
Point FindCentre(Point m, Point n)
{
Point p, mid, centre;
double di2, gao; // 直角三角形的底的平方和高,斜边为1
double jiao; // 斜边与底边的夹角
p.x = m.x - n.x;
p.y = m.y - n.y;
mid.x = (m.x + n.x)/2;
mid.y = (m.y + n.y)/2;
di2 = dis(mid, m);
gao = sqrt(1 - di2);
if(fabs(p.y) < 1e-6) // m, n两点在垂直于x轴的同一垂线上
{
centre.x = mid.x;
centre.y = mid.y + gao;
}
else
{
jiao = atan(-p.x/p.y); // 这里我画图讲解
centre.x = mid.x + gao*cos(jiao);
centre.y = mid.y + gao*sin(jiao);
}
return centre;
}
int main()
{
//freopen("input.txt", "r", stdin);
int ans, tmpans;
double tmp;
Point centre;
scanf("%d", &nCases;);
while(nCases--)
{
ans = 1;
scanf("%d", &nPoints;);
for(int i=0; i 4)
continue;
tmpans = 0;
centre = FindCentre(point[i], point[j]);
for(int k = 0; k < nPoints; ++k)
{
tmp = dis(centre, point[k]);
if(tmp <= 1.000001) tmpans++;
}
if(ans < tmpans)
ans = tmpans;
}
printf("%d\n", ans);
}
return 0;
}
这个是FindCentre的图:
由图可以看到。FindCentre的
di(即直角三角形的底边)是m到mid的值, gao(即直角三角形的高)是centre到mid的值,centre就是到m, n两点距离为1的点,FindCentre的主要部分就是求centre的坐标。可以通过mid点加上偏移的x和y。
而偏移的x, y由jiao(即角度)求出,tan(jiao) = x/y,图中两个角的转换我已经画出,根据初中直角三角形知识知道两个角相等,即可求出偏移的x和y。