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

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 閱讀(762) 評論(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>
            亚洲国产精品久久人人爱蜜臀| 午夜精品三级视频福利| 性色一区二区| 亚洲视频碰碰| 国产日产精品一区二区三区四区的观看方式 | 亚洲国产精品一区在线观看不卡| 久久影院亚洲| 麻豆成人av| 亚洲精品乱码久久久久久久久| 欧美福利在线| 最近看过的日韩成人| 亚洲国产小视频| 欧美日韩综合网| 欧美一区二区在线免费播放| 欧美在线精品一区| 亚洲国产精品一区| 日韩亚洲欧美一区| 国产乱码精品1区2区3区| 久久亚洲一区二区| 欧美精品一区二区在线观看| 亚洲欧美视频在线| 久久福利毛片| 在线视频精品| 久久狠狠亚洲综合| 亚洲精品乱码久久久久久蜜桃91 | 一区二区欧美国产| 国产欧美欧美| 亚洲国产成人久久综合一区| 国产精品成人观看视频国产奇米| 久久国产手机看片| 欧美区国产区| 久久久天天操| 欧美日韩一区二区在线| 久久久久一区| 国产精品theporn88| 欧美1区2区| 国产麻豆成人精品| 亚洲日韩欧美视频| 狠狠色综合播放一区二区| 欧美一区二区三区精品电影| 老色鬼精品视频在线观看播放| 亚洲综合成人在线| 欧美成人免费大片| 久久久精品国产免大香伊| 欧美视频导航| 亚洲黄色在线| 在线播放视频一区| 亚洲欧美日韩在线播放| 亚洲最快最全在线视频| 久色婷婷小香蕉久久| 久久精品道一区二区三区| 欧美亚洲成人精品| 亚洲人午夜精品| 91久久夜色精品国产九色| 久久精品91久久香蕉加勒比| 性感少妇一区| 欧美性理论片在线观看片免费| 欧美激情综合| 91久久精品一区二区别| 久久亚洲一区二区| 久久亚洲高清| 精品成人免费| 久久久中精品2020中文| 久久阴道视频| 黄色成人av网| 久久久亚洲精品一区二区三区| 久久激情五月婷婷| 国产视频自拍一区| 欧美一区日本一区韩国一区| 久久成人精品视频| 国产日本欧美在线观看| 久久国产福利| 老司机精品视频一区二区三区| 狠狠色综合播放一区二区| 久久精品国产精品亚洲| 男人插女人欧美| 亚洲人成在线播放网站岛国| 欧美成人资源| 一本一道久久综合狠狠老精东影业 | 国产欧美一区二区白浆黑人| 亚洲欧美国产另类| 久久精品亚洲热| 狠狠干综合网| 免费成人美女女| 日韩视频免费在线观看| 亚洲欧美三级伦理| 国产综合欧美在线看| 久久久久99| 亚洲国产日韩一区| 亚洲一区二区三区在线视频| 国产精品美女久久福利网站| 久久国产精品99精品国产| 欧美顶级艳妇交换群宴| 在线视频欧美日韩| 国产欧美日韩视频在线观看| 久久精品亚洲热| 亚洲日韩视频| 欧美一区二区在线播放| 亚洲精美视频| 国产精品视频yy9099| 久久天天躁狠狠躁夜夜爽蜜月| 亚洲激情电影在线| 欧美一区二区三区在线观看| 亚洲成人在线视频网站| 国产精品成人一区二区三区夜夜夜| 久久av一区二区| 亚洲国产中文字幕在线观看| 欧美一级淫片播放口| 亚洲精品欧美激情| 国产精品五月天| 免费看亚洲片| 新狼窝色av性久久久久久| 亚洲人成毛片在线播放| 久久精品一本| 亚洲欧美在线一区| 亚洲乱码国产乱码精品精98午夜| 国产麻豆综合| 欧美日韩国产123| 久久久久国色av免费观看性色| 99精品热视频| 亚洲缚视频在线观看| 久久精品一区二区国产| 亚洲欧美日韩一区二区三区在线观看| 136国产福利精品导航| 国产伦精品一区二区三区视频黑人| 免费看的黄色欧美网站| 久久精品日韩| 欧美在线一二三区| 亚洲一区二区视频在线| 亚洲精品视频一区二区三区| 美女国内精品自产拍在线播放| 欧美一区午夜精品| 亚洲一区二区三区免费在线观看 | 亚洲国产激情| 国产亚洲精品自拍| 国产精品区一区| 欧美亚洲不卡| 国产精品国产自产拍高清av王其 | 欧美久久久久中文字幕| 麻豆乱码国产一区二区三区| 久久精品理论片| 午夜在线成人av| 午夜精品久久久久久久久久久久久 | 久久av红桃一区二区小说| 一本色道久久综合狠狠躁篇的优点| 亚洲高清资源综合久久精品| 在线看片日韩| 亚洲第一精品电影| 亚洲国产精品久久久| 在线观看精品视频| 亚洲黄色性网站| 亚洲欧洲在线看| 亚洲另类视频| 亚洲视频精选| 亚洲自拍偷拍色片视频| 亚洲欧美视频在线观看视频| 欧美一级片久久久久久久| 久久精品主播| 老司机凹凸av亚洲导航| 亚洲国产91| 亚洲免费高清| 亚洲综合精品一区二区| 欧美在线视频一区二区三区| 欧美诱惑福利视频| 久久综合久久久久88| 欧美好骚综合网| 欧美性猛交视频| 国产色综合天天综合网| 一区精品久久| 999在线观看精品免费不卡网站| av成人免费| 久久精品视频在线观看| 亚洲第一视频网站| 一区二区三区欧美亚洲| 欧美在线中文字幕| 欧美高清视频在线| 国产精品理论片| 永久免费视频成人| 9l国产精品久久久久麻豆| 性色一区二区| 亚洲第一色在线| 亚洲欧美在线视频观看| 你懂的网址国产 欧美| 国产精品va在线播放| 亚洲第一二三四五区| 亚洲免费在线视频| 六月丁香综合| 亚洲一级免费视频| 免费日韩成人| 国产精品极品美女粉嫩高清在线| 狠狠色综合色区| 亚洲欧美一区二区三区在线| 嫩草国产精品入口| 亚洲一区中文字幕在线观看| 免费欧美日韩| 国产欧美一区二区视频| 夜夜嗨av一区二区三区四季av| 久久久久国产精品人| 中文精品99久久国产香蕉| 欧美1区免费|