POJ 1981
程序员文章站
2022-03-02 10:49:00
...
题目很简单,给定 n 个点,问一个单位圆(半径为 1 的圆)
最多能套住多少个点。
计算几何题目
很暴力的算法。。。枚举。。枚举两个,再跑一边所有点。。。。
虽然很暴力。。但是很好想,还有一种更加优秀的方法,但是目前还没怎么看懂。。。看懂之后再去写。。
这里有一个计算两点之间圆心的函数。。。
point getmid(point p1, point p2)
{
point mid,center;
mid.x = (p1.x + p2.x) / 2.0;
mid.y = (p1.y + p2.y) / 2.0;
double angle = atan2(p1.x - p2.x, p2.y - p1.y); // 从平行四边形的角度去看,求经过中点的那条边的角度
double dcm = sqrt(1-dis(p1, mid) * dis(p1, mid)); // 因为是单位圆,我们要计算出以二者中心为圆心,距离一半为半径的圆的半径和单位圆半径之差
center.x = mid.x + dcm * cos(angle);//三角形思路。。。
center.y = mid.y + dcm * sin(angle);
return center;
}
确实暴力。。但是卡线过了。。
以下为 AC 代码
#include<iostream>
#include<cstdio>
#include<cmath>
using namespace std;
const int maxn = 400;
const double eps = 1e-8;
struct point
{
double x,y;
}a[maxn];
double dis(point a,point b)
{
return sqrt((a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y));
}
point getmid(point p1, point p2)
{
point mid,center;
mid.x = (p1.x + p2.x) / 2.0;
mid.y = (p1.y + p2.y) / 2.0;
double angle = atan2(p1.x - p2.x, p2.y - p1.y);
double dcm = sqrt(1-dis(p1, mid) * dis(p1, mid));
center.x = mid.x + dcm * cos(angle);
center.y = mid.y + dcm * sin(angle);
return center;
}
int main()
{
int n;
while(~scanf("%d",&n) && n)
{
for(int i=0; i<n; i++)
scanf("%lf%lf",&a[i].x,&a[i].y);
int ans = 1;
for(int i=0; i<n; i++)
{
for(int j=i+1; j<n; j++)
{
if(dis(a[i],a[j]) > 2.0)
continue;
point center;
center = getmid(a[i], a[j]);
int cnt = 0;
for(int k=0; k<n; k++)
{
if(dis(a[k], center) < 1.0+eps)
cnt++;
}
ans = max(ans, cnt);
}
}
printf("%d\n",ans);
}
return 0;
}
推荐阅读
-
poj 2689Prime Distance(区间素数)埃氏筛法
-
POJ3252Round Numbers(数位dp)
-
kuangbin专题专题四 Frogger POJ - 2253
-
kuangbin专题 专题一 简单搜索 棋盘问题 POJ - 1321
-
kuangbin专题 专题一 简单搜索 Prime Path POJ - 3126
-
POJ:1017-Packets(贪心+模拟,神烦)
-
poj1637 Sightseeing tour(混合图欧拉回路)
-
POJ1862 Stripies 贪心 B
-
POJ2431 优先队列+贪心 - biaobiao88
-
POJ3233Matrix Power Series(矩阵快速幂)