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

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>
            日韩视频―中文字幕| 国内在线观看一区二区三区| 亚洲激精日韩激精欧美精品| 免费欧美在线| 两个人的视频www国产精品| 亚洲日本中文| 一区二区三区高清视频在线观看| 国产精品国产三级国产专播品爱网| 亚洲欧美在线视频观看| 欧美一区二区在线免费观看| 黄色成人在线| 亚洲国产影院| 欧美日韩在线观看一区二区三区| 亚洲欧美日韩一区二区三区在线观看 | 亚洲高清视频在线观看| 亚洲激情电影中文字幕| 欧美午夜宅男影院| 久久久噜噜噜久久中文字幕色伊伊 | 欧美日本乱大交xxxxx| 中文一区二区| 午夜综合激情| 亚洲精品字幕| 欧美一区二区三区在线观看视频| 亚洲精品乱码久久久久久日本蜜臀| 亚洲视屏在线播放| 亚洲国产美国国产综合一区二区| 亚洲午夜91| 亚洲久久成人| 狠狠色伊人亚洲综合网站色| 日韩视频免费观看高清完整版| 国产主播一区二区三区| 亚洲精品一区二区三区福利| 精品成人一区二区| 亚洲一区二区三区乱码aⅴ| 亚洲大片精品永久免费| 亚洲性感美女99在线| 91久久久国产精品| 欧美在现视频| 校园春色综合网| 欧美日韩无遮挡| 欧美国产日韩免费| 黄色国产精品一区二区三区| 一区二区激情视频| 亚洲精品一区二区三| 欧美专区在线观看| 香蕉乱码成人久久天堂爱免费| 欧美波霸影院| 欧美国产成人精品| 在线成人www免费观看视频| 亚洲欧美国产另类| 亚洲在线中文字幕| 欧美日韩成人精品| 亚洲人体影院| 亚洲日韩成人| 欧美成人官网二区| 欧美福利视频| 亚洲国产一区二区三区高清| 久久久久久一区二区| 久久精品国产96久久久香蕉| 国产精品人人爽人人做我的可爱| 亚洲国产另类久久久精品极度| 亚洲国产乱码最新视频| 久久免费高清| 欧美二区在线看| 亚洲人线精品午夜| 欧美大片在线观看| 亚洲人成毛片在线播放| 99国产精品国产精品毛片| 欧美激情aaaa| 日韩午夜av在线| 亚洲午夜在线观看视频在线| 欧美性猛交99久久久久99按摩 | 亚洲少妇诱惑| 亚洲欧美日韩区| 国产欧美日韩亚州综合| 欧美亚洲日本网站| 久久婷婷国产麻豆91天堂| 韩国久久久久| 欧美大片一区二区| 妖精成人www高清在线观看| 香蕉国产精品偷在线观看不卡| 国产精品一卡二| 久久精品中文字幕一区二区三区| 免费成人av| 一个人看的www久久| 国产精品观看| 久久久久久久久综合| 91久久精品一区二区别| 午夜精品福利电影| 激情久久久久久久| 欧美激情第三页| 亚洲午夜精品在线| 猫咪成人在线观看| 亚洲美女av黄| 国产九九视频一区二区三区| 久久亚洲不卡| 一区二区免费在线观看| 久久免费精品视频| 亚洲人体影院| 久久视频一区二区| 一区二区三区高清在线| 黄色影院成人| 国产精品免费观看视频| 久久在线免费观看| 亚洲一区二区三区在线播放| 欧美成熟视频| 欧美在线高清| 在线中文字幕日韩| 亚洲高清视频的网址| 国产伦精品一区二区三区四区免费| 久久美女性网| 亚洲欧美一区二区三区极速播放| 欧美激情一区二区三区| 欧美一区日本一区韩国一区| 日韩一区二区久久| 狠狠色丁香婷综合久久| 欧美午夜女人视频在线| 久热精品在线| 久久久精品网| 午夜久久久久| 亚洲一区精品视频| 亚洲区第一页| 亚洲国产成人久久| 久久青草欧美一区二区三区| 亚洲一区二区三区影院| 日韩西西人体444www| 一区视频在线看| 狠狠爱成人网| 国产在线精品成人一区二区三区| 国产精品99一区| 欧美日韩在线不卡| 欧美欧美天天天天操| 免费成人在线观看视频| 久久久噜噜噜久久久| 久久激情网站| 久久久久久亚洲精品不卡4k岛国| 亚洲欧洲av一区二区三区久久| 亚洲视频香蕉人妖| 亚洲视频免费| 亚洲视频在线一区| 亚洲永久字幕| 亚洲免费在线观看| 午夜精品国产精品大乳美女| 亚洲欧美区自拍先锋| 亚洲欧美综合v| 先锋影院在线亚洲| 久久电影一区| 久久―日本道色综合久久| 美女诱惑一区| 欧美精品在线视频| 国产精品久久国产愉拍 | 欧美日韩午夜在线| 欧美精品v国产精品v日韩精品| 欧美日本在线播放| 欧美视频中文字幕在线| 国产精品综合不卡av| 国产欧美精品va在线观看| 国产偷国产偷亚洲高清97cao| 激情亚洲网站| 亚洲精品一区二区三区婷婷月 | 久久久国产视频91| 美女视频黄a大片欧美| 亚洲高清不卡在线观看| 日韩视频中文| 欧美在线999| 欧美成人国产一区二区| 国产精品成人播放| 国产日韩在线一区| 在线观看日韩av先锋影音电影院| 亚洲韩国精品一区| 亚洲尤物精选| 免费的成人av| 一本色道综合亚洲| 欧美一区永久视频免费观看| 欧美.www| 国产日韩欧美综合| 亚洲美女精品成人在线视频| 久久成人国产| 欧美日韩爆操| 黄色一区二区三区| 亚洲一级黄色av| 免费欧美在线| 亚洲综合电影一区二区三区| 蜜桃av综合| 国产精品视频一| 日韩亚洲欧美一区二区三区| 久久精品盗摄| 一区二区欧美精品| 麻豆精品一区二区av白丝在线| 国产精品视频导航| 亚洲毛片在线观看.| 免费成人av| 午夜在线不卡| 国产精品区二区三区日本| 亚洲高清中文字幕| 久久一二三国产| 亚洲综合首页| 国产精品第三页| 99亚洲精品| 亚洲国产天堂久久国产91|