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

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 求凸包,再根據夾角,求弧長,而總弧長就是周長。
 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; // 左右鏈必須分開處理,點(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 閱讀(753) 評論(0)  編輯 收藏 引用 所屬分類: ACMAlgorithm課內作業

青青草原综合久久大伊人导航_色综合久久天天综合_日日噜噜夜夜狠狠久久丁香五月_热久久这里只有精品
  • <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>
            欧美国产三级| 欧美一区二区三区视频在线| 久久精品视频在线| 欧美一区二区三区在线播放| 国产精品婷婷| 久久先锋资源| 欧美激情一二三区| 香港久久久电影| 欧美伊人久久| 亚洲三级电影全部在线观看高清| 欧美激情网友自拍| 国产精品久久国产愉拍| 久久激情网站| 欧美另类69精品久久久久9999| 中文有码久久| 久久久www免费人成黑人精品 | 裸体女人亚洲精品一区| 99av国产精品欲麻豆| 中文av一区特黄| 黄色一区二区三区四区| 亚洲人成人99网站| 国产精品美女久久久久久久| 免费在线视频一区| 国产精品美女久久久久久免费| 久久综合99re88久久爱| 欧美三级欧美一级| 女人香蕉久久**毛片精品| 欧美午夜精彩| 亚洲国产精品一区二区尤物区| 国产精品入口福利| 亚洲欧洲偷拍精品| 狠狠噜噜久久| 亚洲主播在线观看| av成人免费在线观看| 久久精品一区四区| 欧美伊人久久| 欧美色另类天堂2015| 欧美成在线观看| 国产在线拍偷自揄拍精品| 亚洲精品一区二区三区蜜桃久 | 欧美第十八页| 美女久久一区| 国产自产v一区二区三区c| 一本久道综合久久精品| 91久久久亚洲精品| 久久久噜噜噜久久中文字幕色伊伊| 亚洲一区二区av电影| 欧美超级免费视 在线| 久久只精品国产| 国产视频在线观看一区二区三区| 日韩视频一区二区三区| 999在线观看精品免费不卡网站| 久久躁狠狠躁夜夜爽| 久热精品视频| 在线播放一区| 久久五月激情| 欧美高清hd18日本| 亚洲国产三级| 欧美国产高清| 亚洲区第一页| 国产精品99久久久久久久久| 欧美激情一区二区三区在线视频| 亚洲第一页在线| 亚洲乱码国产乱码精品精天堂| 媚黑女一区二区| 亚洲国产一区视频| 99精品欧美一区二区三区综合在线| 美女网站在线免费欧美精品| 女仆av观看一区| 亚洲免费观看高清完整版在线观看熊 | 久久精品视频在线| 欧美大片在线看免费观看| 亚洲电影免费观看高清完整版在线 | 欧美一激情一区二区三区| 欧美一区二区三区视频免费| 国产欧美日韩专区发布| 欧美一区二区高清| 欧美成人精品1314www| 最新日韩中文字幕| 欧美三区美女| 欧美影院视频| 亚洲国产国产亚洲一二三| 亚洲视频狠狠| 国产亚洲一区在线播放| 狼狼综合久久久久综合网| 亚洲成人资源| 亚洲欧美一区二区激情| 国内精品久久久久久久果冻传媒 | 一区二区三区你懂的| 久久久国产亚洲精品| 亚洲欧洲一级| 国产美女搞久久| 免费看黄裸体一级大秀欧美| 亚洲区一区二| 久久久久久久久久久久久久一区 | 激情成人综合网| 欧美日韩精品一区二区在线播放| 亚洲影视在线播放| 亚洲电影自拍| 久久精品国产v日韩v亚洲 | 国产精品美女久久久浪潮软件| 羞羞色国产精品| 亚洲人成网站精品片在线观看| 欧美亚洲一区三区| 日韩视频不卡| 激情亚洲成人| 国产精品一区二区你懂得| 久久全球大尺度高清视频| 一个色综合导航| 欧美国产亚洲精品久久久8v| 午夜欧美视频| 一区二区三区四区五区精品| 韩国成人精品a∨在线观看| 欧美三级乱码| 欧美精品午夜视频| 久久综合99re88久久爱| 亚洲免费人成在线视频观看| 日韩视频中文| 亚洲国产高清在线| 欧美成年人视频| 久久国产精品久久精品国产| 在线亚洲观看| 夜夜精品视频| 日韩视频一区二区| 亚洲欧洲一区| 亚洲精品久久久久中文字幕欢迎你| 国产亚洲毛片在线| 国产女精品视频网站免费| 欧美三级资源在线| 欧美日韩日本网| 欧美日韩国产精品成人| 免费av成人在线| 噜噜噜在线观看免费视频日韩| 欧美伊人久久久久久久久影院 | 一个色综合av| 亚洲午夜精品在线| 亚洲午夜精品17c| 亚洲私人黄色宅男| 亚洲主播在线播放| 亚洲专区欧美专区| 亚洲欧美日本在线| 西瓜成人精品人成网站| 亚洲女人小视频在线观看| 亚洲女女做受ⅹxx高潮| 午夜精品福利一区二区三区av| 亚洲一区二区三区精品动漫| 亚洲一区三区视频在线观看 | 久久青草久久| 欧美福利在线观看| 亚洲精品一二| 亚洲在线免费| 久久久久国产精品厨房| 麻豆国产精品va在线观看不卡| 欧美成人xxx| 欧美三级电影精品| 国产亚洲欧洲997久久综合| 国产一区二区精品丝袜| 亚洲国产成人av| 一区二区免费在线观看| 亚洲一区国产精品| 久久久水蜜桃| 亚洲国产欧美一区二区三区同亚洲 | 伊人精品在线| 一区二区三区四区国产| 亚洲欧美激情视频| 久久影音先锋| 亚洲巨乳在线| 欧美制服丝袜第一页| 蜜桃久久av| 国产精品色婷婷| 亚洲国产高清高潮精品美女| 99视频一区二区三区| 久久成人免费网| 亚洲第一在线| 午夜欧美大尺度福利影院在线看| 久久久国产一区二区| 欧美日韩中文字幕在线| 狠狠综合久久| 亚洲综合第一页| 欧美成人小视频| 午夜精品久久久久久99热| 免费成人av资源网| 国产人成一区二区三区影院| 亚洲人成在线播放| 久久精选视频| 亚洲无亚洲人成网站77777| 玖玖玖免费嫩草在线影院一区| 国产精品久久久久久久浪潮网站| 亚洲大胆美女视频| 久久国产色av| 中文在线一区| 欧美精品久久久久久久久老牛影院 | 久久婷婷国产综合国色天香| 国产精品久久久久久久久借妻 | 亚洲自拍偷拍色片视频| 亚洲国产美国国产综合一区二区| 午夜精品免费在线| 国产精品成人一区二区| 亚洲精品乱码久久久久| 米奇777在线欧美播放|