最小圆覆盖模板

//最小圆覆盖
//输入: 从下标0开始的点集_ps和大小_n
//输出: 覆盖所有点的最小圆
//复杂度: O(n)
//注意: 会对_ps进行随机处理操作，将会改变点集的内部顺序
Circle MinCoverCir(Point _ps[],int _n)
{
    //随机处理，但是会改变传入的点集。
    random_shuffle(_ps, _ps+_n);//复杂度O(_n)
    
    Circle rec;
    rec.r = 0;
    rec.c = _ps[0];
    for(int i=1;i<_n;i++)
    {
        if(GT( Dis(rec.c,_ps[i]),rec.r ) )//i点在圆外
        {
            rec.r = 0;
            rec.c = _ps[i];
            for(int j=0;j<i;j++)
            {
                if( GT( Dis(rec.c,_ps[j]),rec.r ) )//j在圆外
                {
                    rec.c.x = (_ps[i].x+_ps[j].x)/2.0;
                    rec.c.y = (_ps[i].y+_ps[j].y)/2.0;
                    rec.r = Dis(_ps[i],_ps[j])/2.0;
                    for(int k=0;k<j;k++)
                    {
                        if( GT( Dis(rec.c,_ps[k]),rec.r ) )//k在圆外
                        {
                            rec=OutCircle(_ps[i], _ps[j], _ps[k]);
                        }
                    }
                }
            }
        }
    }
    return rec;
}