HDU 1077

题意 : 给你 N 个点, 问一个单位圆最大能包括几个点

直接暴力枚举圆心, 计算个数        O(n^ 3);

精度,细节都要注意,

//#include<bit/stdc++.h>
//using namespace std;
#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<cmath>
#include<queue>
#include<stack>
#include<set>
#include<vector>
#include<map>
#include<algorithm>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const int maxn = 400;
const double eps = 1e-4; struct Point
{
double x, y;
}Num[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 cen1,cen2; void GetCen(Point a,Point b)
{
double x0 = (a.x + b.x) / 2;
double y0 = (a.y + b.y) / 2;
double d = sqrt(1-((a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y))/4);
if(fabs(a.y - b.y) < 1e-9) ///在同一水平线上
{
cen1.x = x0;
cen1.y = y0 + d;
cen2.x = x0;
cen2.y = y0 - d;
}
else /// 额外计算圆心,先算角
{
double tmp = atan(-(a.x - b.x)/(a.y - b.y));
double dx = d * cos(tmp); /// X 的 变化
double dy = d * sin(tmp); /// Y 的 变化
cen1.x = x0 + dx;
cen1.y = y0 + dy;
cen2.x = x0 - dx;
cen2.y = y0 - dy;
}
} int main()
{
int t, n;
scanf("%d",&t);
while(t--)
{
scanf("%d",&n);
for(int i = 0; i < n; ++i)
scanf("%lf%lf",&Num[i].x,&Num[i].y);
int ans = 1;
for(int i = 0; i < n; ++i)
{
for(int j = i+1; j < n; ++j)
{
if(Dis(Num[i],Num[j]) > 2.0) continue;
GetCen(Num[i],Num[j]);
int cnt = 2;
for(int k = 0; k < n; ++k)
if(k != i && k != j && Dis(cen1,Num[k]) < 1+eps) cnt++;
if(cnt > ans) ans = cnt;
cnt = 2;
////////////////////
for(int k = 0; k < n; ++k)
if(k != i && k != j && Dis(cen2,Num[k]) < 1+eps) cnt++;
if(cnt > ans) ans = cnt;
}
}
printf("%d\n",ans);
}
return 0;
}

(debug到………)

上一篇:ASP.NET MVC导入excel到数据库


下一篇:北大青鸟进入ASP.NET MVC的世界(一)