午夜欧美精品,在线看日韩欧美,欧美日韩一区国产

POJ 2402- A Star not a Tree?(費馬點)

#include <cstdio>
2

#include <cmath>
3

const int SIZE = 102;
5

struct TPoint
7

{
8

double x ;
9

double y ;
10

} ;
11

TPoint point[SIZE];
13

int N;
14

double 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

double GetALLDist( const TPoint& p, const int& n )
21

{
22

int i;
23

double sum = 0.0;
24

for ( i = 0; i < n; ++i )
26

sum += Distance( p, point[i] );
27

return sum;
29

}
30

double GetFermatPoint( const int& n )
32

{
33

TPoint st = point[0];
34

TPoint tmp, nt;
35

double t, step = 100, fermat = GetALLDist(st, n);
36

while ( step > 0.2 )
38

{
39

int ok = 1;
40

while ( ok ) {
42

ok = 0;
43

nt = st;
44

tmp.x = st.x, tmp.y = st.y + step;
46

t = GetALLDist(tmp, n);
48

if ( t < fermat )
50

{
51

fermat = t;
52

ok = 1;
53

nt = tmp;
54

}
55

tmp.x = st.x, tmp.y = st.y - step;
57

t = GetALLDist(tmp, n);
59

if ( t < fermat )
60

{
61

fermat = t;
62

ok = 1;
63

nt = tmp;
64

}
65

tmp.x = st.x + step, tmp.y = st.y;
67

t = GetALLDist(tmp, n);
69

if ( t < fermat )
71

{
72

fermat = t;
73

ok = 1;
74

nt = tmp;
75

}
76

tmp.x = st.x - step, tmp.y = st.y;
78

t = GetALLDist(tmp, n);
80

if ( t < fermat )
81

{
82

fermat = t;
83

ok = 1;
84

nt = tmp;
85

}
86

st = nt;
88

}
89

step /= 2.0;
91

}
92

return fermat;
94

}
95

int 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 巫閱讀(297) 評論(0) 編輯收藏引用所屬分類: 幾何

只有注冊用戶登錄后才能發表評論。
【推薦】100%開源！大型工業跨平臺軟件C++源碼提供，建模，組態！



網站導航: 博客園 IT新聞 BlogJava 博問 Chat2DB 管理

gzwzm06

常用鏈接

留言簿(3)

隨筆檔案

文章分類

文章檔案

搜索

最新評論