gzwzm06
  C++博客 :: 首页 :: 新随笔 :: 联系 :: 聚合  :: 管理 ::
  1 随笔 :: 52 文章 :: 17 评论 :: 0 Trackbacks
POJ 2402- A Star not a Tree?(费马点)
  1#include <cstdio>
  2#include <cmath>
  3
  4const int SIZE = 102;
  5
  6struct TPoint
  7{
  8    double x ;
  9    double y ;
 10} ;
 11
 12TPoint point[SIZE];
 13int N;
 14
 15double Distance( const TPoint& p1, const TPoint& p2 )
 16{
 17    return sqrt((p1.x - p2.x) * (p1.x - p2.x) + (p1.y - p2.y) * (p1.y - p2.y)) ;
 18}
 19
 20double GetALLDist( const TPoint& p, const int& n )
 21{
 22    int i;
 23    double sum = 0.0;
 24
 25    for ( i = 0; i < n; ++i )
 26        sum += Distance( p, point[i] );
 27
 28    return sum;
 29}
 30
 31double GetFermatPoint( const int& n )
 32{
 33    TPoint st = point[0];
 34    TPoint tmp, nt;
 35    double t, step = 100, fermat = GetALLDist(st, n);
 36
 37    while ( step > 0.2 )
 38    {
 39        int ok = 1;
 40
 41        while ( ok ) {
 42            ok = 0;
 43            nt = st;
 44
 45            tmp.x = st.x, tmp.y = st.y + step;
 46
 47            t = GetALLDist(tmp, n);
 48
 49            if ( t < fermat )
 50            {
 51                fermat = t;
 52                ok = 1;
 53                nt = tmp;
 54            }
 55
 56            tmp.x = st.x, tmp.y = st.y - step;
 57
 58            t = GetALLDist(tmp, n);
 59            if ( t < fermat )
 60            {
 61                fermat = t;
 62                ok = 1;
 63                nt = tmp;
 64            }
 65
 66            tmp.x = st.x + step, tmp.y = st.y;
 67
 68            t = GetALLDist(tmp, n);
 69
 70            if ( t < fermat )
 71            {
 72                fermat = t;
 73                ok = 1;
 74                nt = tmp;
 75            }
 76
 77            tmp.x = st.x - step, tmp.y = st.y;
 78
 79            t = GetALLDist(tmp, n);
 80            if ( t < fermat )
 81            {
 82                fermat = t;
 83                ok = 1;
 84                nt = tmp;
 85            }
 86            
 87            st = nt;
 88        }
 89
 90        step /= 2.0;
 91    }
 92
 93    return fermat;
 94}
 95
 96int main()
 97{
 98    int i, ans;
 99    double t;
100
101    scanf("%d", &N);
102
103    for ( i = 0; i < N; ++i )
104    {
105        scanf("%lf %lf", &point[i].x, &point[i].y);
106    }
107
108    t = GetFermatPoint( N );
109
110    ans = (int)(t + 0.5) * 100 / 100;
111
112    printf("%d\n", ans);
113
114    return 0;
115}
posted on 2009-03-31 12:08 巫 阅读(279) 评论(0)  编辑 收藏 引用 所属分类: 几何

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理