• <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>
            

    
            

            




            







												


        


            


            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< int, int > 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 閱讀(743) 評論(0)  編輯 收藏 引用  所屬分類: ACM 、Algorithm 、課內作業 
		
            
	
            
	
	





            
	    
    




            






            

				

            


    
    







            
	   
	



日本加勒比久久精品|
99久久久精品|
伊人久久大香线蕉综合影院首页|
国产香蕉久久精品综合网|
久久综合亚洲欧美成人|
一本伊大人香蕉久久网手机|
久久久久亚洲?V成人无码|
久久亚洲精精品中文字幕|
久久久久亚洲AV成人网|
精品无码久久久久久尤物|
午夜肉伦伦影院久久精品免费看国产一区二区三区
|
久久超乳爆乳中文字幕|
久久人搡人人玩人妻精品首页|
奇米影视7777久久精品|
亚洲欧洲久久av|
亚洲国产精品久久久久婷婷软件
|
久久久久国产精品人妻|
久久精品中文字幕一区|
97久久天天综合色天天综合色hd|
模特私拍国产精品久久|
久久亚洲中文字幕精品一区四|
久久精品aⅴ无码中文字字幕不卡|
亚洲国产成人乱码精品女人久久久不卡|
人妻久久久一区二区三区|
久久精品国产男包|
亚州日韩精品专区久久久|
欧美激情精品久久久久久久九九九|
久久无码av三级|
丁香五月综合久久激情|
国产福利电影一区二区三区久久久久成人精品综合
|
久久国产精品无码网站|
91精品免费久久久久久久久|
日韩欧美亚洲综合久久影院d3|
精品综合久久久久久97超人|
久久精品国产亚洲AV无码偷窥|
久久婷婷五月综合97色一本一本
|
久久夜色tv网站|
精品欧美一区二区三区久久久|
精品久久久无码中文字幕|
久久人人爽人人澡人人高潮AV|
久久午夜无码鲁丝片午夜精品|