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

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)  編輯 收藏 引用 所屬分類: ACM 、Algorithm 、課內作業

青青草原综合久久大伊人导航_色综合久久天天综合_日日噜噜夜夜狠狠久久丁香五月_热久久这里只有精品
  • <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>
            亚洲毛片播放| 欧美日本国产一区| 国产日本欧美视频| 欧美在线观看视频| 午夜精品久久久久影视| 国产亚洲精品bt天堂精选| 欧美一区二区三区四区在线观看地址 | 久久成人羞羞网站| 国内精品伊人久久久久av一坑| 麻豆精品视频在线观看视频| 久久一区二区三区超碰国产精品| 亚洲黄色在线视频| 中文在线一区| 狠狠干综合网| aa成人免费视频| 国产三级欧美三级日产三级99| 裸体一区二区| 欧美视频在线观看免费网址| 久久久xxx| 欧美理论大片| 久久久久久久999精品视频| 欧美成人国产| 欧美在线视频网站| 欧美国产综合视频| 欧美综合77777色婷婷| 麻豆freexxxx性91精品| 欧美亚洲视频在线观看| 麻豆国产精品777777在线 | 国产乱理伦片在线观看夜一区| 久久综合色8888| 欧美亚州韩日在线看免费版国语版| 久久精品中文字幕免费mv| 欧美另类综合| 美日韩免费视频| 国产精品天天看| 亚洲精品一区二区三区蜜桃久| 国产一区视频观看| 亚洲视频一起| 99热免费精品| 免费日韩视频| 久久精品视频免费播放| 国产精品国产三级欧美二区| 亚洲第一精品久久忘忧草社区| 国产精品一区二区男女羞羞无遮挡| 亚洲成色www久久网站| 国产一区二区三区丝袜 | 亚洲国产黄色| 伊人精品久久久久7777| 亚洲欧美日韩精品久久亚洲区| 一区二区三区|亚洲午夜| 农夫在线精品视频免费观看| 麻豆精品一区二区综合av| 国产日韩欧美在线看| 亚洲视频网在线直播| 亚洲在线视频免费观看| 欧美日韩一区二| 亚洲精品偷拍| 亚洲美女视频在线观看| 欧美风情在线观看| 亚洲欧洲日本mm| 99综合在线| 欧美日韩成人一区二区三区| 亚洲另类在线一区| 亚洲图片欧美一区| 国产精品美女久久久久久免费| 亚洲精品一区二区三| 中文网丁香综合网| 欧美日韩在线一区| 一本大道久久a久久精二百| 中日韩美女免费视频网址在线观看| 欧美激情一区二区三区在线视频 | 久久精品最新地址| 黄色日韩网站视频| 免费观看国产成人| 日韩视频一区二区三区在线播放| 日韩午夜一区| 欧美性做爰毛片| 午夜精品国产更新| 久久亚洲私人国产精品va媚药| 在线成人中文字幕| 欧美精品日韩| 亚洲欧美日韩视频二区| 久久久久五月天| 亚洲国产精品女人久久久| 欧美国产激情二区三区| 亚洲私人影吧| 鲁大师成人一区二区三区| 亚洲黄网站黄| 国产精品亚洲一区| 久久久久久尹人网香蕉| 日韩亚洲综合在线| 欧美一区二粉嫩精品国产一线天| 国产日韩欧美在线观看| 欧美大片在线观看| 亚洲桃色在线一区| 欧美国产欧美综合| 西西人体一区二区| 亚洲黄色尤物视频| 国产性天天综合网| 欧美高清视频www夜色资源网| 一区二区三区四区国产| 久久久国产一区二区| 亚洲精品视频在线看| 国产精品一区二区男女羞羞无遮挡| 久久综合色婷婷| 亚洲在线视频网站| 欧美成人亚洲成人| 欧美一区二区三区视频在线观看 | 欧美亚洲一区二区在线| 91久久精品国产| 国产亚洲观看| 欧美午夜精品久久久久久久| 久久综合久久88| 亚洲综合电影| 一道本一区二区| 亚洲黄网站在线观看| 久久久夜色精品亚洲| 亚洲永久精品国产| 亚洲美女黄网| 一区在线播放| 国产精品一区=区| 欧美日韩国产色站一区二区三区| 久久久综合网| 欧美亚洲日本网站| 亚洲性线免费观看视频成熟| 亚洲高清在线| 欧美国产综合一区二区| 浪潮色综合久久天堂| 久久国产免费| 欧美在线日韩| 午夜在线一区二区| 亚洲欧美日韩精品在线| 亚洲免费观看视频| 亚洲精品乱码久久久久久蜜桃麻豆| 国产视频久久久久久久| 国产精品嫩草影院一区二区| 国产精品99免费看 | 久久成人这里只有精品| 亚洲综合社区| 亚洲欧美成人一区二区在线电影 | 亚洲精品国产品国语在线app| 亚洲二区在线观看| 欧美激情综合色| 欧美激情精品久久久久久蜜臀| 麻豆国产va免费精品高清在线| 久久久噜噜噜久久| 久久露脸国产精品| 麻豆精品视频在线观看| 欧美国产日产韩国视频| 亚洲国产精品成人综合| 亚洲国产精品va在线观看黑人| 欧美激情精品久久久久久久变态 | 午夜精品国产更新| 欧美影院精品一区| 久久精品亚洲乱码伦伦中文 | 一区二区三区福利| 亚洲欧美国产高清va在线播| 欧美一级免费视频| 狂野欧美一区| 亚洲成人资源网| 一区二区三区欧美| 羞羞色国产精品| 麻豆91精品| 国产精品高潮呻吟久久| 国产日韩欧美中文| 亚洲国产欧洲综合997久久| 日韩一级黄色大片| 午夜在线不卡| 免费看精品久久片| 一区二区三区精品在线| 欧美在线免费看| 欧美国产三区| 国产精品视频最多的网站| 激情成人av| 在线一区免费观看| 久久久久久久综合日本| 亚洲黄色尤物视频| 亚洲欧美99| 欧美激情网友自拍| 国产日韩欧美麻豆| 亚洲免费电影在线| 久久久久国产一区二区三区| 亚洲国产激情| 欧美中文字幕视频在线观看| 欧美激情91| 黄色一区二区三区| 亚洲影院高清在线| 欧美激情一区二区三区在线视频观看 | 久久夜色撩人精品| 一区二区日韩伦理片| 老鸭窝亚洲一区二区三区| 国产精品久久久久毛片软件| 亚洲国产高清高潮精品美女| 亚洲欧美日韩在线一区| 亚洲国产婷婷香蕉久久久久久| 亚洲男人的天堂在线| 欧美日韩国产限制| 亚洲人体1000| 蜜臀99久久精品久久久久久软件| 亚洲欧美日韩精品久久久|