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

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>
            久久综合狠狠综合久久综合88| 久久久久久久久一区二区| 欧美成人中文| 99国产精品久久久| 一区二区欧美精品| 国产视频一区在线观看| 美女诱惑一区| 欧美日韩成人一区二区| 欧美一级成年大片在线观看| 午夜精品美女自拍福到在线| 在线日韩一区二区| 99re66热这里只有精品3直播| 国产精品久久久久7777婷婷| 久久久久久久一区二区| 久久综合亚州| 亚洲欧美视频在线观看视频| 欧美一区久久| 夜夜嗨av一区二区三区| 亚洲综合首页| 亚洲毛片在线观看| 欧美一级播放| 一本一本久久a久久精品牛牛影视| 亚洲一区日韩在线| 亚洲国产欧美日韩另类综合| 亚洲午夜激情网页| 亚洲经典一区| 午夜精品久久久久影视 | 另类av导航| 亚洲欧美另类国产| 美日韩丰满少妇在线观看| 亚洲一区二区三区视频播放| 久久人人爽国产| 欧美一区二区三区在线免费观看| 免费成人网www| 欧美一区二区三区视频免费播放| 欧美高清视频一区二区| 久久经典综合| 国产精品扒开腿爽爽爽视频| 亚洲国产日本| 国产揄拍国内精品对白| 夜夜爽www精品| 亚洲欧洲一二三| 欧美一区二区成人| 亚洲在线观看免费| 欧美精品一区在线观看| 欧美3dxxxxhd| 国内自拍亚洲| 欧美中文在线免费| 久久成人精品| 国产伦精品一区二区三区视频孕妇 | 亚洲综合国产激情另类一区| 美女精品在线观看| 噜噜噜噜噜久久久久久91 | 欧美电影打屁股sp| 欧美国产视频在线观看| 精品成人国产| 久久久久久久综合日本| 久久久久五月天| 国内精品久久久久久久果冻传媒 | 亚洲欧美精品在线| 午夜精品久久99蜜桃的功能介绍| 欧美日本国产精品| 最新日韩在线| 99精品黄色片免费大全| 欧美日韩成人| 日韩一区二区电影网| 亚洲午夜久久久久久久久电影网| 欧美日韩一区二区三区| 99精品久久免费看蜜臀剧情介绍| 亚洲无亚洲人成网站77777| 欧美日韩一区二区三区免费看| 亚洲九九爱视频| 中文一区二区| 国产免费观看久久| 久久精品成人一区二区三区| 欧美激情一区二区三级高清视频 | 久久综合久久综合这里只有精品 | 99这里只有久久精品视频| 欧美母乳在线| 亚洲午夜未删减在线观看| 久久精品夜夜夜夜久久| 在线观看视频一区二区| 欧美不卡高清| 亚洲午夜在线| 久久美女性网| 亚洲精品国产精品乱码不99| 欧美日韩国产999| 亚洲影院一区| 欧美激情视频给我| 亚洲制服av| 激情欧美一区二区| 欧美日韩国产一区| 性8sex亚洲区入口| 亚洲国产欧美一区| 亚洲欧美日韩一区二区在线 | 欧美日韩中文字幕日韩欧美| 午夜精品久久久久久久99水蜜桃 | 欧美全黄视频| 久久国产精品网站| 亚洲精品中文字幕女同| 久久精品官网| 一区二区三区成人| 激情成人av| 欧美性大战久久久久久久蜜臀| 久久av二区| 国产精品99久久99久久久二8| 美女精品国产| 欧美怡红院视频| 99视频热这里只有精品免费| 国精品一区二区三区| 欧美日韩日日夜夜| 噜噜噜久久亚洲精品国产品小说| 亚洲无人区一区| 亚洲区一区二| 免费欧美在线视频| 久久国产精彩视频| 亚洲午夜视频在线观看| 亚洲经典视频在线观看| 激情视频亚洲| 国产午夜精品全部视频在线播放| 欧美日韩视频一区二区三区| 另类综合日韩欧美亚洲| 欧美一区高清| 欧美夜福利tv在线| 亚洲尤物在线视频观看| 日韩亚洲欧美高清| 亚洲国产精品成人综合| 欧美电影免费观看网站| 久久久久久尹人网香蕉| 欧美在线3区| 久久av老司机精品网站导航| 亚洲欧美日韩国产| 亚洲一区日本| 亚洲影院污污.| 亚洲免费影视第一页| 一区二区精品国产| 夜夜爽av福利精品导航| 亚洲卡通欧美制服中文| 最新国产精品拍自在线播放| 在线播放一区| 亚洲第一精品福利| 亚洲国产精品久久久| 亚洲国产经典视频| 亚洲精品日韩久久| 亚洲美女中文字幕| 亚洲无玛一区| 欧美一区二区日韩| 久久久高清一区二区三区| 久久九九免费| 欧美成人免费va影院高清| 亚洲电影免费在线观看| 亚洲精品一区二区三区在线观看| 日韩午夜黄色| 亚洲在线中文字幕| 欧美在线视频二区| 免费视频久久| 欧美日韩一级片在线观看| 国产精品视频免费| 黄网动漫久久久| 亚洲理论在线观看| 亚洲免费小视频| 久久亚洲精品欧美| 亚洲人成亚洲人成在线观看| 亚洲色图在线视频| 久久不见久久见免费视频1| 蜜臀av国产精品久久久久| 欧美韩日亚洲| 国产精品夜夜嗨| 亚洲高清在线| 亚洲午夜免费视频| 久久久久久一区二区| 亚洲国产精品电影在线观看| 亚洲无线视频| 免费亚洲婷婷| 国产精品视频免费在线观看| 激情综合在线| 亚洲一区二区三区免费视频| 快播亚洲色图| 一区二区日韩免费看| 久久久亚洲影院你懂的| 欧美日韩在线播放一区| 精品不卡一区| 亚洲欧美日韩一区| 亚洲国产高潮在线观看| 午夜欧美不卡精品aaaaa| 欧美电影免费| 激情小说亚洲一区| 亚洲欧美日韩直播| 亚洲欧洲精品一区二区三区不卡 | 欧美日韩免费视频| 尤物视频一区二区| 欧美一区视频| 99国产一区| 欧美激情一区二区三区高清视频| 国产一区二区三区在线播放免费观看| 99在线精品观看| 亚洲福利视频免费观看| 欧美在线免费观看| 国产麻豆精品视频| 亚洲与欧洲av电影|