青青草原综合久久大伊人导航_色综合久久天天综合_日日噜噜夜夜狠狠久久丁香五月_热久久这里只有精品

coreBugZJ

此 blog 已棄。

EOJ 1189 Wall POJ 1113 Wall

  1/*
  2EOJ 1189 Wall
  3POJ 1113 Wall
  4
  5
  6----問題描述:
  7
  8Once 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
 10Your 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
 12The 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
 14
 15----輸入:
 16
 17Input 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
 19Next 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 
 21Process to end of file. 
 22
 23
 24----輸出:
 25
 26For 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
 28
 29----樣例輸入:
 30
 319 100
 32200 400
 33300 400
 34300 300
 35400 300
 36400 400
 37500 400
 38500 200
 39350 200
 40200 200 
 41
 42
 43----樣例輸出:
 44
 451628
 46
 47
 48----分析:
 49
 50Graham-Scan 求凸包,再根據(jù)夾角,求弧長(zhǎng),而總弧長(zhǎng)就是周長(zhǎng)。
 51
 52
 53*/

 54
 55
 56#include <iostream>
 57#include <cstdio>
 58#include <cmath>
 59#include <algorithm>
 60
 61using namespace std;
 62
 63// #define  TEST
 64
 65#define  N  1009
 66typedef  pair< intint > Point;
 67#define  y  first
 68#define  x  second
 69#define  PI  3.14159265358979
 70
 71int    n;
 72int    le;
 73Point  p[ N ];
 74
 75double solve() {
 76        static Point stk[ N ];
 77        int    tp, i, ntp;
 78        double ans = 0;
 79
 80        sort( p, p+n );
 81
 82#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
 88        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; // 左右鏈必須分開處理,點(diǎn)(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
138int 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 閱讀(756) 評(píng)論(0)  編輯 收藏 引用 所屬分類: ACMAlgorithm課內(nèi)作業(yè)

青青草原综合久久大伊人导航_色综合久久天天综合_日日噜噜夜夜狠狠久久丁香五月_热久久这里只有精品
  • <ins id="pjuwb"></ins>
    <blockquote id="pjuwb"><pre id="pjuwb"></pre></blockquote>
    <noscript id="pjuwb"></noscript>
          <sup id="pjuwb"><pre id="pjuwb"></pre></sup>
            <dd id="pjuwb"></dd>
            <abbr id="pjuwb"></abbr>
            亚洲最新视频在线| 亚洲尤物在线| 欧美国产日本| 久久米奇亚洲| 亚洲人成在线观看网站高清| 91久久精品国产91性色| 欧美成人性网| 亚洲一区精品视频| 午夜一区二区三区不卡视频| 国产一级揄自揄精品视频| 久久精品一本| 欧美aⅴ99久久黑人专区| 99精品视频免费全部在线| 一区二区三区日韩欧美精品| 欧美新色视频| 麻豆精品传媒视频| 欧美乱大交xxxxx| 欧美一区二区三区四区高清| 久久狠狠亚洲综合| 亚洲国产精品久久人人爱蜜臀| 亚洲免费精品| 影院欧美亚洲| 在线亚洲欧美专区二区| 伊人成年综合电影网| 亚洲欧洲日本在线| 国产午夜精品全部视频在线播放 | 亚洲欧洲在线免费| 亚洲激情影院| 国产香蕉久久精品综合网| 欧美凹凸一区二区三区视频| 欧美天堂在线观看| 免费看的黄色欧美网站| 国产精品久久久久久久久果冻传媒| 狼狼综合久久久久综合网| 欧美日韩1区2区3区| 另类激情亚洲| 国产精品入口麻豆原神| 91久久综合| 激情综合中文娱乐网| 99re热这里只有精品视频| 在线免费观看日韩欧美| 亚洲一区二区三区精品视频| 99国产精品久久久久久久| 久久国产黑丝| 欧美在线三级| 国产精品高清网站| 亚洲九九精品| 亚洲人成在线播放网站岛国| 欧美一区二区性| 性欧美大战久久久久久久久| 欧美女主播在线| 欧美国产日韩精品免费观看| 国产亚洲va综合人人澡精品| 亚洲影视九九影院在线观看| 亚洲午夜精品久久| 欧美va亚洲va日韩∨a综合色| 久久亚洲精品一区二区| 国产九九精品视频| 亚洲欧美日韩视频二区| 亚洲在线免费| 国产精品久久久亚洲一区 | 99国产精品自拍| 日韩一区二区精品视频| 久久人人九九| 裸体一区二区三区| 在线观看一区二区精品视频| 欧美中文在线免费| 久久久久久亚洲精品中文字幕| 国产欧美91| 先锋影音国产一区| 久久亚洲精品网站| 亚洲第一精品夜夜躁人人爽| 久久久噜噜噜久久久| 嫩草影视亚洲| 亚洲精品欧美日韩专区| 欧美激情视频一区二区三区在线播放 | 国产一区二区精品丝袜| 欧美一区二区三区四区在线| 久久精品视频免费| 激情综合电影网| 欧美不卡高清| 一本大道久久a久久综合婷婷 | 9l视频自拍蝌蚪9l视频成人| 欧美精品一区二区三区久久久竹菊| 亚洲人午夜精品免费| 亚洲一区二区精品| 国产精品专区第二| 久久久av水蜜桃| 亚洲人屁股眼子交8| 欧美一级大片在线免费观看| 国产亚洲亚洲| 欧美国产日韩一区二区| 一本色道久久| 久久综合色影院| 99国产精品视频免费观看| 国产精品美女久久久久av超清| 欧美一站二站| 亚洲黄色三级| 欧美在线视频观看| 亚洲人成人77777线观看| 国产精品啊v在线| 久久久97精品| 99精品视频一区| 免费观看在线综合| 亚洲欧美精品一区| 亚洲第一网站免费视频| 国产精品多人| 欧美激情日韩| 久久国产99| 亚洲一区免费视频| 欧美大尺度在线| 欧美一级二区| 一区二区三区国产精品| 尹人成人综合网| 国产精品视频免费在线观看| 免费人成精品欧美精品| 午夜在线观看免费一区| 亚洲人成77777在线观看网| 久久伊人精品天天| 亚洲主播在线观看| 99视频一区二区| 亚洲福利视频网站| 国产日韩欧美视频| 国产精品av一区二区| 免费成人高清在线视频| 久久成人精品无人区| 一个色综合导航| 亚洲人成啪啪网站| 亚洲东热激情| 欧美成人精品h版在线观看| 久久er精品视频| 午夜精品久久久久久久99热浪潮| 亚洲精品无人区| 亚洲欧洲在线视频| 亚洲国产一区二区a毛片| 国内自拍视频一区二区三区| 国产麻豆成人精品| 国产精品欧美日韩一区| 欧美视频专区一二在线观看| 欧美日韩国产色视频| 欧美韩日一区二区| 欧美国产日韩一区二区三区| 蜜桃av噜噜一区| 久久综合伊人77777麻豆| 久久久久久久精| 欧美主播一区二区三区美女 久久精品人| 亚洲主播在线| 欧美在线三级| 久久久精品午夜少妇| 久久精品夜夜夜夜久久| 久久精品国产77777蜜臀| 久久黄金**| 久久久久久久久综合| 久久五月天婷婷| 欧美黄色大片网站| 欧美日韩综合视频| 欧美视频一区二区三区四区| 国产精品另类一区| 国产亚洲一区二区三区在线播放| 国产亚洲欧美一级| 在线播放中文字幕一区| 亚洲精品网址在线观看| 亚洲一区www| 久久精品视频在线播放| 狂野欧美一区| 亚洲日本理论电影| 亚洲视频碰碰| 在线看片成人| 亚洲每日在线| 欧美一二区视频| 亚洲三级色网| 一区二区高清视频| 午夜日韩在线| 老司机一区二区三区| 亚洲日韩欧美视频一区| 一区二区三区鲁丝不卡| 欧美在线精品免播放器视频| 女人香蕉久久**毛片精品| 欧美日韩在线观看一区二区| 国产欧美精品va在线观看| 在线观看的日韩av| 亚洲综合999| 欧美不卡视频| 亚洲免费小视频| 欧美国产亚洲精品久久久8v| 国产精品毛片a∨一区二区三区|国| 伊人天天综合| 亚洲一区二区三区视频播放| 久久综合网络一区二区| 日韩视频在线一区| 久久久久九九视频| 国产精品美女久久久免费| 亚洲福利在线看| 久久www成人_看片免费不卡| 亚洲黄色视屏| 久久综合99re88久久爱| 国产目拍亚洲精品99久久精品| 91久久综合| 免费国产自线拍一欧美视频| 午夜激情久久久|