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

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>
            亚洲美女网站| 亚洲综合不卡| 欧美日韩一区二区三区在线看| 久久久久这里只有精品| 久久精品视频在线播放| 久久久久久久999| 久久婷婷国产麻豆91天堂| 久久久综合免费视频| 久久综合一区| 欧美日韩1234| 国产精品一区二区欧美| 国产一区二区激情| 伊人激情综合| 99精品视频免费| 亚洲欧美在线磁力| 久久综合九色99| 亚洲精品1区2区| 99精品国产热久久91蜜凸| 亚洲专区在线视频| 麻豆国产va免费精品高清在线| 欧美人妖在线观看| 国产一区二区激情| 国产精品99久久久久久有的能看| 久久精品亚洲精品| 亚洲激情网站免费观看| 亚洲欧美一区二区三区极速播放| 麻豆九一精品爱看视频在线观看免费 | 久久人人看视频| 亚洲一区二区三区久久| 欧美日韩一本到| 国产一区二区三区成人欧美日韩在线观看| 亚洲福利精品| 先锋影音国产精品| 亚洲国产专区校园欧美| 欧美一区二区高清在线观看| 欧美激情亚洲自拍| 一区在线观看视频| 羞羞答答国产精品www一本| 亚洲黑丝在线| 久久一区二区视频| 国产亚洲综合精品| 亚洲欧美影音先锋| 日韩一区二区精品| 欧美黄色影院| 亚洲国产精品福利| 老司机一区二区三区| 中文在线一区| 欧美日韩人人澡狠狠躁视频| 亚洲欧洲日夜超级视频| 久久夜色精品国产欧美乱| 99视频日韩| 欧美精品国产精品日韩精品| 狠狠v欧美v日韩v亚洲ⅴ| 欧美在线在线| 亚洲欧美日韩系列| 国产精品一区二区男女羞羞无遮挡 | 亚洲精品偷拍| 欧美精品一级| 99国产精品久久| 亚洲成人直播| 免费不卡在线观看| 亚洲啪啪91| 亚洲国产专区校园欧美| 欧美高清视频免费观看| 亚洲精品永久免费精品| 亚洲日本电影在线| 欧美日韩成人在线视频| 亚洲香蕉伊综合在人在线视看| 亚洲国产精品成人| 欧美精品久久99久久在免费线| 亚洲久久视频| 99综合在线| 国产欧美韩日| 久久全球大尺度高清视频| 久久xxxx| 亚洲国产婷婷| 亚洲免费大片| 国产精品呻吟| 久久免费精品日本久久中文字幕| 久久精品天堂| 亚洲美女av网站| 一区二区三区国产| 国产日产亚洲精品| 欧美a级片一区| 欧美日韩在线播放| 欧美在线视频在线播放完整版免费观看 | 亚洲日韩中文字幕在线播放| 欧美日韩成人在线| 欧美伊人久久久久久久久影院| 亚洲欧美日韩天堂一区二区| 激情欧美一区二区| 亚洲人www| 国产乱码精品一区二区三| 欧美成人xxx| 国产精品分类| 欧美国产亚洲精品久久久8v| 国产精品mm| 你懂的亚洲视频| 国产精品va在线播放| 六月婷婷一区| 国产精品天天看| 亚洲国产美女久久久久| 国产欧美一区二区精品性色| 亚洲国产视频直播| 黑人操亚洲美女惩罚| 中日韩视频在线观看| 在线看片第一页欧美| 亚洲网友自拍| 最新亚洲激情| 久久精品亚洲国产奇米99| 一区二区高清在线| 久久久蜜桃一区二区人| 午夜伦理片一区| 欧美日本在线| 欧美成人综合一区| 国产深夜精品福利| 亚洲美女尤物影院| 1769国内精品视频在线播放| 亚洲主播在线播放| 一本色道久久加勒比精品| 久久久噜噜噜久噜久久 | 国产精品视频一二| 亚洲精品影院在线观看| 亚洲电影专区| 久久精品成人一区二区三区| 亚洲一区二区三区四区五区午夜 | 亚洲激情啪啪| 另类春色校园亚洲| 久久亚洲春色中文字幕久久久| 国产九区一区在线| 亚洲午夜在线| 亚洲你懂的在线视频| 欧美伦理在线观看| 亚洲人成艺术| 一区二区欧美国产| 欧美区二区三区| 亚洲激情影视| 亚洲免费观看在线观看| 欧美成人免费全部观看天天性色| 农夫在线精品视频免费观看| 国产欧美日韩| 一区二区免费在线播放| 欧美高清不卡在线| 亚洲电影欧美电影有声小说| 影音先锋成人资源站| 久久精品一二三区| 另类人畜视频在线| 国产专区欧美专区| 久久精品99| 免费在线观看成人av| 在线看欧美日韩| 欧美精品97| 亚洲乱码国产乱码精品精天堂| 在线视频亚洲一区| 国产精品一区二区在线观看网站 | 正在播放亚洲| 国产精品久久夜| 欧美在线欧美在线| 欧美v国产在线一区二区三区| 亚洲激情电影中文字幕| 欧美日韩在线播放三区| 亚洲女同在线| 欧美成人高清视频| 一区二区日韩| 国产午夜精品麻豆| 女女同性精品视频| 亚洲午夜精品久久久久久浪潮| 久久精品九九| 亚洲精品一区二区三| 国产精品三区www17con| 免费不卡亚洲欧美| 亚洲欧美日韩国产中文在线| 欧美高清影院| 欧美在线播放一区| 夜色激情一区二区| 一区二区三区在线视频免费观看| 欧美日韩在线播放三区四区| 久久久久国色av免费观看性色| 一本到12不卡视频在线dvd| 久久婷婷蜜乳一本欲蜜臀| 亚洲私人影吧| 亚洲欧洲日产国产综合网| 国产亚洲福利社区一区| 欧美日韩国产色视频| 久久精品网址| 在线视频亚洲欧美| 欧美国产一区二区三区激情无套| 亚洲综合日本| 亚洲三级电影在线观看| 国产女主播一区二区| 欧美巨乳波霸| 久久综合伊人77777蜜臀| 午夜视频一区在线观看| 亚洲美女91| 亚洲国产精品视频一区| 久久精品欧美日韩精品| 午夜激情亚洲| 亚洲欧美一区二区三区久久| 日韩视频在线一区二区三区| 伊人男人综合视频网|