coreBugZJ

此 blog 已棄。

EOJ 1189 Wall POJ 1113 Wall

/*
2

EOJ 1189 Wall
3

POJ 1113 Wall
4

----問題描述：
7

Once upon a time there was a greedy King who ordered his chief Architect to build a wall around the King's castle. The King was so greedy, that he would not listen to his Architect's proposals to build a beautiful brick wall with a perfect shape and nice tall towers. Instead, he ordered to build the wall around the whole castle using the least amount of stone and labor, but demanded that the wall should not come closer to the castle than a certain distance. If the King finds that the Architect has used more resources to build the wall than it was absolutely necessary to satisfy those requirements, then the Architect will loose his head. Moreover, he demanded Architect to introduce at once a plan of the wall listing the exact amount of resources that are needed to build the wall.
9

Your task is to help poor Architect to save his head, by writing a program that will find the minimum possible length of the wall that he could build around the castle to satisfy King's requirements.
11

The task is somewhat simplified by the fact, that the King's castle has a polygonal shape and is situated on a flat ground. The Architect has already established a Cartesian coordinate system and has precisely measured the coordinates of all castle's vertices in feet.
13

----輸入：
16

Input contains several test cases. The first line of each case contains two integer numbers N and L separated by a space. N (3 <= N <= 1000) is the number of vertices in the King's castle, and L (1 <= L <= 1000) is the minimal number of feet that King allows for the wall to come close to the castle.
18

Next N lines describe coordinates of castle's vertices in a clockwise order. Each line contains two integer numbers Xi and Yi separated by a space (-10000 <= Xi, Yi <= 10000) that represent the coordinates of ith vertex. All vertices are different and the sides of the castle do not intersect anywhere except for vertices.
20

Process to end of file.
22

----輸出：
25

For each case in the input, write to the output file the single number that represents the minimal possible length of the wall in feet that could be built around the castle to satisfy King's requirements. You must present the integer number of feet to the King, because the floating numbers are not invented yet. However, you must round the result in such a way, that it is accurate to 8 inches (1 foot is equal to 12 inches), since the King will not tolerate larger error in the estimates.
27

----樣例輸入：
30

9 100
32

200 400
33

300 400
34

300 300
35

400 300
36

400 400
37

500 400
38

500 200
39

350 200
40

200 200
41

----樣例輸出：
44

1628
46

----分析：
49

Graham-Scan 求凸包，再根據夾角，求弧長，而總弧長就是周長。
51

*/
54

#include <iostream>
57

#include <cstdio>
58

#include <cmath>
59

#include <algorithm>
60

using namespace std;
62

// #define TEST
64

#define N 1009
66

typedef pair< int, int > Point;
67

#define y first
68

#define x second
69

#define PI 3.14159265358979
70

int n;
72

int le;
73

Point p[ N ];
74

double solve() {
76

static Point stk[ N ];
77

int tp, i, ntp;
78

double ans = 0;
79

sort( p, p+n );
81

#ifdef TEST
83

for ( i = 0; i < n; ++i ) {
84

printf( "x = %d y = %d\n", p[ i ].x, p[ i ].y );
85

}
86

#endif
87

tp = 0;
89

stk[ tp ] = p[ 0 ];
90

for ( i = 1; i < n; ++i ) {
91

while ( (0 < tp) &&
92

((stk[tp].x-stk[tp-1].x)*(p[i].y-stk[tp].y) -
93

(p[i].x-stk[tp].x)*(stk[tp].y-stk[tp-1].y) <= 0)
94

) {
95

--tp;
96

}
97

++tp;
98

stk[ tp ] = p[ i ];
99

}
100

101

#ifdef TEST
102

printf( "stk 1\n" );
103

for ( i = 0; i <= tp; ++i ) {
104

printf( "stk x = %d y = %d\n", stk[ i ].x, stk[ i ].y );
105

}
106

#endif
107

108

ntp = tp; // 左右鏈必須分開處理，點(n-1)左右鏈共用
109

for ( i = n-2; i >= 0; --i ) {
110

while ( (ntp < tp) &&
111

((stk[tp].x-stk[tp-1].x)*(p[i].y-stk[tp].y) -
112

(p[i].x-stk[tp].x)*(stk[tp].y-stk[tp-1].y) <= 0)
113

) {
114

--tp;
115

}
116

++tp;
117

stk[ tp ] = p[ i ];
118

}
119

120

#ifdef TEST
121

printf( "stk all\n" );
122

for ( i = 0; i <= tp; ++i ) {
123

printf( "stk x = %d y = %d\n", stk[ i ].x, stk[ i ].y );
124

}
125

#endif
126

127

for ( i = 0; i < tp; ++i ) {
128

ans += sqrt((double)(
129

(stk[i].x-stk[i+1].x)*(stk[i].x-stk[i+1].x)
130

+ (stk[i].y-stk[i+1].y)*(stk[i].y-stk[i+1].y)
131

));
132

}
133

134

ans += 2 * PI * le;
135

return ans;
136

}
137

138

int main() {
139

int i;
140

while ( 2 == scanf( "%d%d", &n, &le ) ) {
141

for ( i = 0; i < n; ++i ) {
142

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

}
144

printf( "%0.0lf\n", solve() );
145

}
146

return 0;
147

}
148

posted on 2012-05-13 22:52 coreBugZJ 閱讀(742) 評論(0) 編輯收藏引用所屬分類: ACM 、Algorithm 、課內作業

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

相關文章: 微軟2014實習生及秋令營技術類職位在線測試 TopCoder SRM 593 DIV2 第三題生成全排列的非回溯方法（TopCoder SRM 591 DIV 2） A* 算法求解八數碼問題，POJ 1077 Eight POJ 1067 取石子游戲 POJ 2068 Nim POJ 2975 Nim POJ 3696 The Luckiest number POJ 3604 Professor Ben EOJ 1117 剩余定理

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

coreBugZJ

My Links

Blog Stats

常用鏈接

留言簿(10)

隨筆分類(458)

隨筆檔案(268)

相冊

ACM

AI

LaTeX

安全

編程語言

好有道理

技術

開源

科學

數學

圖形圖像

文化

問題（練習＆有趣）

資源

最新隨筆

搜索

最新評論

閱讀排行榜

評論排行榜

EOJ 1189 Wall POJ 1113 Wall