2017 CCPC 哈尔滨 M ( hdu 6242) Geometry Problem (随机化 + 三角形外心) - wchhlbt的博客 - CSDN博客

文章价值(3) ?
阅读数(510) ?

解题思路:看到1/2这个概率可以很容易想到随机化的算法,每次随机一个三元组,表示从n个点中随机选取三个点,然后判断这三个点的外接圆是不是满足题意的点。可以证明的是选取三个点不能构成这么一个圆的概率是(1-1/8) = 7/8 . 那么选取100次还没找到这个圆的概率已经是1e-6,近似为0.所以算法的复杂度得到证明。


Tips: 比赛的时候一直以为是精度问题导致Wrong Answer,没有注意考虑算法细节,其实是没有考虑小于等于4个点的情况,这种情况下即使几个点共线,选取两个点的中点也是满足题意的。


AC代码:

/*
* @Author: wchhlbt
* @Last Modified time: 2017-11-11
*/

#include 

#define inf 0x3f3f3f3f
#define pb push_back
#define AA first
#define BB second
#define ONES(x) __builtin_popcount(x)
#define _  << " " <<
using namespace std;

typedef pair P;
typedef long long ll ;
int dx[4] = {0,0,1,-1};
int dy[4] = {1,-1,0,0};
const double eps =1e-6;
const int mod = 1000000007;
const double PI = acos(-1.0);
inline int read(){ int num;    scanf("%d",&num);   return num;}
const int maxn = 100007;

//判断x的符号 零、正、负
int sgn(double x)
{
    if(fabs(x) < eps)return 0;
    if(x < 0)return -1;
    else return 1;
}

typedef struct Point
{
    double x,y;
    Point() {} ;
    Point(double _x,double _y):x(_x),y(_y) {};
    //两点相减,返回一个向量; 两向量相减,返回向量的差
    Point operator -(const Point &b) const{
        return Point(x - b.x,y - b.y);
    }
    //两向量相加,返回向量的和
    Point operator +(const Point &b) const{
        return Point(x + b.x,y + b.y);
    }
    bool operator < (const Point &a)const{
        if(a.x==x) return y=(n+1)/2)    return true;
    else    return false;
}

int main()
{
    srand(time(NULL));
    int t = read();
    while(t--){
        int n = read();
        for(int i = 0; i1e9 || abs(cp.y)>1e9)  continue;
            double r = dist(cp,p[a]);
            if( check(n, cp, r) ){
                //cout << cp.x _ cp.y _ r << endl;
                printf("%.12f %.12f %.12f\n",cp.x,cp.y,r);
                break;
            }
        }
    }
    return 0;
}






(注:此网站文章大都来自公开的博客,如有原作者发现有侵权问题,请在此留言,我们会立刻删除相关文章。)

我的评价: