2015年3月2日 星期一

[TIOJ 1254] 砲打皮皮2

作法:

題目就是要求最小包含圓的半徑,向上取整,之前有聽說有O(n)的隨機算法,但還沒看QQ 只想到O(n^3)的作法,感覺過不了,所以只好用爬山法唬爛(?)

簡單來說要找的東西是一個點(圓心)到所有點的距離的最大值最小,考慮隨機取一個點,往他的 8 方位跑 len 長度,如果答案變小了就更新,如果沒有更小的答案就把 len 除掉 2 ,一直做下去就可以了。

code :

#include<bits/stdc++.h>
#define DB double
using namespace std;
const int maxn=1000+10 ;
struct pt{DB x,y;};
 
pt operator - (const pt &a,const pt &b) { return (pt){a.x-b.x,a.y-b.y}; }
DB length(const pt &a) { return sqrt(a.x*a.x+a.y*a.y) ; }
 
int n,m ;
int dx[]={1,1,0,-1,-1,-1,0,1} ;
int dy[]={0,1,1,1,0,-1,-1,-1} ;
pt a[maxn*maxn] ;
 
DB cal(const pt &p)
{
    DB ret=0.0 ;
    for(int i=1;i<=m;i++) ret=max(ret,length(p-a[i])) ;
    return ret ;
}
 
main()
{
    while(scanf("%d%d",&n,&m)==2 && n+m)
    {
        DB x0=0.0,y0=0.0 ;
        for(int i=1;i<=m;i++)
            scanf("%lf%lf",&a[i].x,&a[i].y) ,
            x0+=a[i].x , y0+=a[i].y ;
        x0/=m , y0/=m ;
        DB val=cal((pt){x0,y0}) ;
        for(DB len=1.0;len>1e-1;len*=0.5)
        {
            DB x1,y1 ;
            while(1)
            {
                bool found=0 ;
                DB nx,ny ;
                for(int i=0;i<8;i++)
                {
                    nx=x0+len*dx[i] , ny=y0+len*dy[i] ;
                    DB tmp=cal((pt){nx,ny}) ;
                    if(tmp>=val) continue ;
                    found=1 ; x1=nx ; y1=ny ;
                    val=tmp ;
                }
                if(!found) break ;
                else x0=x1 , y0=y1 ;
            }
        }
        val+=1e-5 ;
        printf("%d\n",int(ceil(val)+1e-5)) ;
    }
}
 

1 則留言:

  1. If you want your ex-girlfriend or ex-boyfriend to come crawling back to you on their knees (no matter why you broke up) you gotta watch this video
    right away...

    (VIDEO) Win your ex back with TEXT messages?

    回覆刪除