hdu1077-单位圆覆盖最多点
zjhl2
posted @ 2015年12月12日 00:53
with tags
计算几何
, 570 阅读
做计算几何好苦。。。。。。
题意:用半径为1的圆覆盖最多的点
枚举两个点构造出圆使得这两点在圆上,判断覆盖了多少点。复杂度O(n^3)
一直WA,以为是被卡精度了,后来看了kuangbin的题解才知道忘记考虑n==1时答案为1的情况,思维有缺陷,思维品质不高啊。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 | # include <cstdio> # include <iostream> # include <cmath> # include <algorithm> #define eps 1e- 4 using namespace std; int t,n,i,j; struct dot{ double x,y; }a[ 305 ]; double sqr(double x){ return x*x;} double dis(double ax,double ay,double bx,double by) { return sqrt(sqr(ax-bx)+sqr(ay-by)); } int get (double x,double y) { int cnt= 0 ; for ( int i= 1 ;i<=n;i++) if (dis(x,y,a[i].x,a[i].y)<= 1 +eps) cnt++; return cnt; } int main() { scanf( "%d" ,&t); while (t--) { scanf( "%d" ,&n); for (i= 1 ;i<=n;i++) scanf( "%lf%lf" ,&a[i].x,&a[i].y); int ans= 1 ; for (i= 1 ;i<n;i++) for (j=i+ 1 ;j<=n;j++) { double d=dis(a[i].x,a[i].y,a[j].x,a[j].y)/ 2 ; if (d> 1 ) continue ; double sita=acos(d); double ang=atan2(a[j].y-a[i].y,a[j].x-a[i].x); double x=a[i].x+cos(ang-sita),y=a[i].y+sin(ang-sita); ans=max(ans, get (x,y)); x=a[i].x+cos(ang+sita);y=a[i].y+sin(ang+sita); ans=max(ans, get (x,y)); } printf( "%d\n" ,ans); } } |