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

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ù)夾角,求弧長,而總弧長就是周長。
 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 閱讀(760) 評論(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>
            国产精品美女黄网| 国产免费观看久久| 亚洲电影成人| 欧美激情精品久久久久久黑人| 老司机精品导航| 亚洲欧洲一区二区在线观看| 亚洲激情在线激情| 欧美精品七区| 亚洲综合精品自拍| 午夜视频久久久久久| 韩日午夜在线资源一区二区| 欧美电影免费观看| 欧美日韩精品三区| 欧美一区三区二区在线观看| 久久国产精品久久久久久| 在线精品视频一区二区三四| 亚洲人成在线免费观看| 国产精品久久久久久久久久ktv| 欧美一区日韩一区| 老鸭窝毛片一区二区三区 | 这里是久久伊人| 国产精品色婷婷| 欧美aⅴ一区二区三区视频| 欧美精品18videos性欧美| 小辣椒精品导航| 老司机久久99久久精品播放免费| 亚洲视频在线观看网站| 欧美在线观看你懂的| 亚洲精品视频啊美女在线直播| 亚洲视频第一页| 亚洲激情校园春色| 午夜激情亚洲| 中文在线不卡视频| 久久久夜夜夜| 欧美在线观看视频在线| 欧美久久精品午夜青青大伊人| 久久久夜夜夜| 欧美调教视频| 亚洲国产一区二区三区高清| 国产一区二区三区在线观看免费视频| 亚洲欧洲在线免费| 一区二区三区在线免费观看| 亚洲视频欧洲视频| 亚洲精品一区二区在线| 久久精品人人做人人爽| 亚洲欧美一区二区视频| 欧美欧美全黄| 欧美激情一区二区三区蜜桃视频| 国产欧美日韩一级| 一本色道久久综合| 99精品欧美一区二区蜜桃免费| 久久精品视频在线看| 欧美一区二区视频在线观看2020| 欧美屁股在线| 亚洲黄色尤物视频| 亚洲国产免费| 久久综合久久综合久久综合| 久久久噜噜噜| 国产在线国偷精品产拍免费yy| 在线亚洲欧美视频| 亚洲一区免费| 国产精品v日韩精品| 一本色道久久综合亚洲精品不卡 | 伊人成人在线视频| 欧美一区二区三区免费大片| 欧美亚洲自偷自偷| 国产精品亚洲一区| 亚洲在线观看免费| 欧美永久精品| 国产亚洲激情| 久久精品国产综合精品| 老司机67194精品线观看| 很黄很黄激情成人| 久久久欧美精品sm网站| 你懂的视频一区二区| 136国产福利精品导航| 久久伊人精品天天| 亚洲国产精品福利| 99re66热这里只有精品4| 欧美日韩一区综合| 午夜在线不卡| 美女精品在线| 亚洲精品久久久蜜桃| 欧美日本免费| 亚洲一区国产视频| 久久先锋资源| 99精品久久久| 国产乱码精品1区2区3区| 久久久久九九视频| 亚洲精品免费网站| 性久久久久久久久| 精东粉嫩av免费一区二区三区| 免费观看国产成人| 亚洲视频狠狠| 裸体一区二区| 在线视频日本亚洲性| 国产一级一区二区| 欧美国产欧美亚州国产日韩mv天天看完整| 亚洲日本va午夜在线影院| 亚洲欧美精品suv| 伊人久久噜噜噜躁狠狠躁| 欧美激情亚洲综合一区| 亚洲尤物视频网| 亚洲国产精品久久久久婷婷老年| 亚洲欧美国产三级| 亚洲国产成人精品视频| 国产精品福利网站| 久久婷婷人人澡人人喊人人爽 | 欧美在线三级| 亚洲伦理中文字幕| 国产三级欧美三级| 欧美日韩国产精品| 久久综合久久88| 亚洲欧美中文日韩在线| 亚洲国产成人久久综合| 久久精品国产亚洲aⅴ| 亚洲精品视频一区| 黄色欧美成人| 国产精品素人视频| 欧美日韩国产不卡在线看| 久久久久久久久一区二区| 亚洲一级在线观看| 日韩一级精品| 亚洲成在人线av| 麻豆精品精品国产自在97香蕉| 亚洲在线观看| 亚洲午夜精品久久久久久浪潮| 亚洲国产精品传媒在线观看| 国产日韩欧美夫妻视频在线观看| 欧美日韩精品一区二区在线播放| 美日韩在线观看| 久久久久国产精品午夜一区| 亚洲欧洲av一区二区| 亚洲手机视频| 一本大道久久a久久综合婷婷| 亚洲电影在线免费观看| 免费看av成人| 老司机午夜精品视频在线观看| 欧美专区福利在线| 欧美一区国产二区| 欧美一区2区视频在线观看| 亚洲一区黄色| 亚洲欧美日韩一区二区在线 | 亚洲第一伊人| 伊人一区二区三区久久精品| 国产亚洲精品成人av久久ww| 国产美女搞久久| 国产小视频国产精品| 国产日韩成人精品| 国产主播一区| 尤物视频一区二区| 亚洲国产欧美一区二区三区同亚洲| 激情一区二区三区| 樱桃成人精品视频在线播放| 在线观看一区欧美| 亚洲欧洲日本国产| 一本色道久久综合狠狠躁篇的优点| 日韩网站在线| 亚洲欧美日韩国产综合| 亚洲欧美日韩国产一区二区三区| 午夜精品在线视频| 久久久久综合网| 欧美成人日韩| 999在线观看精品免费不卡网站| 一区二区三区视频在线观看| 亚洲一二区在线| 久久久久欧美精品| 欧美激情第3页| 欧美日韩一区二区三区在线看| 国产精品三级视频| 国内精品视频在线播放| 亚洲精品三级| 亚洲欧美日本国产有色| 久久综合色一综合色88| 最新高清无码专区| 亚洲欧美一区二区三区极速播放| 久久久久久网| 欧美色图首页| 黄色一区二区三区四区| 一区二区三区毛片| 久久亚洲不卡| 99视频一区| 久久综合网hezyo| 国产精品日韩在线观看| 亚洲高清123| 香蕉久久久久久久av网站| 你懂的一区二区| 亚洲午夜av电影| 巨乳诱惑日韩免费av| 国产精品免费一区豆花| 亚洲黄网站在线观看| 欧美一级片一区| 亚洲国产精品久久久久秋霞蜜臀| 亚洲欧美日韩专区| 欧美精品一区在线| 在线观看精品视频| 久久av一区| 国产精品99久久不卡二区| 欧美xxx成人| 在线观看亚洲视频|