Maple trees

Time Limit: 1000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 1847 Accepted Submission(s): 574

Problem Description

There are a lot of trees in HDU. Kiki want to surround all the trees with the minimal required length of the rope . As follow,

To
make this problem more simple, consider all the trees are circles in a
plate. The diameter of all the trees are the same (the diameter of a
tree is 1 unit). Kiki can calculate the minimal length of the rope ,
because it's so easy for this smart girl.
But we don't have a rope to
surround the trees. Instead, we only have some circle rings of
different radius. Now I want to know the minimal required radius of the
circle ring. And I don't want to ask her this problem, because she is
busy preparing for the examination.
As a smart ACMer, can you help me ?

Input

The
input contains one or more data sets. At first line of each input data
set is number of trees in this data set n （1 <= n <= 100）, it is
followed by n coordinates of the trees. Each coordinate is a pair of
integers, and each integer is in [-1000, 1000], it means the position of
a tree’s center. Each pair is separated by blank.
Zero at line for number of trees terminates the input for your program.

Output

Minimal required radius of the circle ring I have to choose. The precision should be 10^-2.

Sample Input

2
1 0
-1 0
0

Sample Output

1.50

题意：求将所有树包括进来的最小圆的半径,最后要加上树本身的半径(树的直径为1).

最小圆覆盖问题：

一.概念引入

最小包围圆问题：对于给定的平面上甩个点所组成的一个集合P，求出P的最小包围圆，即包含P中所有点、半径最小

的那个圆。也就是求出这个最小包围圆的圆心位置和半径。

下面是若干性质。

1.有限点集P的最小包围圆是唯一的。这里约定，若P中只有一个点v，则最小包围圆是退化的，其半径为0，圆心为点v。

2.非退化最小包围圆可以由2个或者3个边界点定义。边界上只有两个点，则必定是直径两端，其它点都在圆内部。

3.点集P中，距离最大的2个点A、B不一定都在边界上，但是必有d≥|AB|。

4.直角三角形或钝角三角形的3个顶点的最小包围圆是以最长边为直径的圆；锐角三角形3个顶点的最小包围圆是三角形

的外接圆。

5.新加入点一定在圆上。
以上资料参考:http://www.cnblogs.com/hxsyl/p/3226562.html

hdu 2215

///最小圆覆盖问题：

/**一.概念引入

最小包围圆问题：对于给定的平面上甩个点所组成的一个集合P，求出P的最小包围圆，即包含P中所有点、半径最小

的那个圆。也就是求出这个最小包围圆的圆心位置和半径。

下面是若干性质。

1.有限点集P的最小包围圆是唯一的。这里约定，若P中只有一个点v，则最小包围圆是退化的，其半径为0，圆心为点v。

2.非退化最小包围圆可以由2个或者3个边界点定义。边界上只有两个点，则必定是直径两端，其它点都在圆内部。

3.点集P中，距离最大的2个点A、B不一定都在边界上，但是必有d≥|AB|。

4.直角三角形或钝角三角形的3个顶点的最小包围圆是以最长边为直径的圆；锐角三角形3个顶点的最小包围圆是三角形

的外接圆。

5.新加入点一定在圆上。

*/

#include <iostream>

#include <cstdio>

#include <string.h>

#include <math.h>

#include <algorithm>

using namespace std;

const int N = ;

const double eps = 1e-;

struct Point{

    double x,y;

}p[N];

Point c; ///这是最小圆的圆心

double r; ///这是最小圆半径

int n;

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 circumcenter(Point a,Point b,Point c){

    Point ret=a;

    double a1 = (b.x-a.x),b1=(b.y-a.y),c1 = (a1*a1+b1*b1)/;

    double a2 = (c.x-a.x),b2=(c.y-a.y),c2 = (a2*a2+b2*b2)/;

    double d=a1*b2-a2*b1;

    ret.x+=(c1*b2-c2*b1)/d;

    ret.y+=(a1*c2-a2*c1)/d;

    return ret;

}

void min_cover_circle(){

    //random_shuffle(p,p+n); ///模板上面的这个函数是打乱点，这个题不要比要还快15MS

    c = p[],r = ;

    for(int i=;i<n;i++){ ///i是第一个点

        if(dis(p[i],c)-r>eps){

            c = p[i],r=;

            for(int j=;j<i;j++){ ///j是第二个点

                if(dis(p[j],c)-r>eps){

                   c.x = (p[i].x+p[j].x)/;

                   c.y = (p[i].y+p[j].y)/;

                   r = dis(p[j],c);

                   for(int k=;k<j;k++){ ///k是第三个点

                        if(dis(p[k],c)-r>eps){

                            c = circumcenter(p[i],p[j],p[k]);

                            r = dis(p[i],c);

                        }

                   }

                }

            }

        }

    }

}

int main()

{

    while(scanf("%d",&n)!=EOF&&n){

        for(int i=;i<n;i++){

            scanf("%lf%lf",&p[i].x,&p[i].y);

        }

        min_cover_circle();

        printf("%.2lf\n",r+0.5);

    }

    return ;

}

hdu 3932

///最小圆覆盖问题：

/**一.概念引入

最小包围圆问题：对于给定的平面上甩个点所组成的一个集合P，求出P的最小包围圆，即包含P中所有点、半径最小

的那个圆。也就是求出这个最小包围圆的圆心位置和半径。

下面是若干性质。

1.有限点集P的最小包围圆是唯一的。这里约定，若P中只有一个点v，则最小包围圆是退化的，其半径为0，圆心为点v。

2.非退化最小包围圆可以由2个或者3个边界点定义。边界上只有两个点，则必定是直径两端，其它点都在圆内部。

3.点集P中，距离最大的2个点A、B不一定都在边界上，但是必有d≥|AB|。

4.直角三角形或钝角三角形的3个顶点的最小包围圆是以最长边为直径的圆；锐角三角形3个顶点的最小包围圆是三角形

的外接圆。

5.新加入点一定在圆上。

*/

#include <iostream>

#include <cstdio>

#include <string.h>

#include <math.h>

#include <algorithm>

using namespace std;

const int N = ;

const double eps = 1e-;

struct Point{

    double x,y;

}p[N];

Point c; ///这是最小圆的圆心

double r; ///这是最小圆半径

int n;

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 circumcenter(Point a,Point b,Point c){

    Point ret=a;

    double a1 = (b.x-a.x),b1=(b.y-a.y),c1 = (a1*a1+b1*b1)/;

    double a2 = (c.x-a.x),b2=(c.y-a.y),c2 = (a2*a2+b2*b2)/;

    double d=a1*b2-a2*b1;

    ret.x+=(c1*b2-c2*b1)/d;

    ret.y+=(a1*c2-a2*c1)/d;

    return ret;

}

void min_cover_circle(){

    //random_shuffle(p,p+n); ///模板上面的这个函数是打乱点，这个题不要比要还快15MS

    c = p[],r = ;

    for(int i=;i<n;i++){ ///i是第一个点

        if(dis(p[i],c)-r>eps){

            c = p[i],r=;

            for(int j=;j<i;j++){ ///j是第二个点

                if(dis(p[j],c)-r>eps){

                   c.x = (p[i].x+p[j].x)/;

                   c.y = (p[i].y+p[j].y)/;

                   r = dis(p[j],c);

                   for(int k=;k<j;k++){ ///k是第三个点

                        if(dis(p[k],c)-r>eps){

                            c = circumcenter(p[i],p[j],p[k]);

                            r = dis(p[i],c);

                        }

                   }

                }

            }

        }

    }

}

int main()

{

    int X,Y;

    while(scanf("%d%d%d",&X,&Y,&n)!=EOF){

        for(int i=;i<n;i++){

            scanf("%lf%lf",&p[i].x,&p[i].y);

        }

        min_cover_circle();

        printf("(%.1lf,%.1lf).\n%.1lf\n",c.x,c.y,r);

    }

    return ;

}

巴特西

hdu 2215 & hdu 3932(最小覆盖圆)

Maple trees

最新文章

热门文章