• <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 1708 Connected Gheeves
		
            
		
              1/*
              2EOJ 1708 Connected Gheeves
              3
              4
              5----問題描述：
              6
              7Gheeves (plural of gheef) are some objects similar to funnels. We define a gheef as a two dimensional object specified by a sequence of points (p1, p2, , pn) with the following conditions:
              8
              9 1. 3 ≤ n ≤ 1000
             10 2. If a point pi is specified by the coordinates (xi, yi), there is an index 1 < c < n such that y1 > y2 >  > yc and yc < yc+1 < yc+2 <  < yn. pc is called the cusp of the gheef.
             11 3. For all 1 ≤ i < c, xi < xc and for all c < i ≤ n, xi > xc.
             12 4. For 1 < i < c, the amount of rotation required to rotate pi-1 around pi in clockwise direction to become co-linear with pi and pi+1, is greater than 180 degrees. Likewise, for c < i < n, the amount of rotation required to rotate pi-1 around pi in clockwise rotation to become co-linear with pi and pi+1, is greater than 180 degrees.
             13 5. The set of segments joining two consecutive points of the sequence intersect only in their endpoints.
             14
             15We call the sequence of segments (p1p2, p2p3, , pn-1pn), the body of the gheef. In this problem, we are given two gheeves P = (p1, p2, , pn) and Q = (q1, q2, , qm), such that all x coordinates of pi are negative integers and all x coordinates of qi are positive integers. Assuming the cusps of the two gheeves are connected with a narrow pipe, we pour a certain amount of water inside the gheeves. As we pour water, the gheeves are filled upwards according to known physical laws (the level of water in two gheeves remains the same). Note that in the gheef P, if the level of water reaches min(y1, yn), the water pours out of the gheef (the same is true for the gheef Q). Your program must determine the level of water in the two gheeves after pouring a certain amount of water. Since we have defined our problem in two dimensions, the amount of water is measured in terms of area it fills. Note that the volume of pipe connecting cusps is considered as zero.
             16
             17
             18----輸入：
             19
             20The first number in the input line, t is the number of test cases. Each test case is specified on three lines of input. The first line contains a single integer a (1 ≤ a ≤ 100000) which specifies the amount of water poured into two gheeves. The next two lines specify the two gheeves P and Q respectively, each of the form k x1 y1 x2 y2  xk yk where k is the number of points in the gheef (n for P and m for Q), and the xi yi sequence specify the coordinates of the points in the sequences.
             21
             22
             23----輸出：
             24
             25The output contains t lines, each corresponding to an input test case in that order. The output line contains a single integer L indicating the final level of water, expressed in terms of y coordinates rounded to three digits after decimal points.
             26
             27
             28----樣例輸入：
             29
             302
             3125
             323 -30 10 -20 0 -10 10
             333 10 10 20 0 30 10
             3425
             353 -30 -10 -20 -20 -10 -10
             363 10 10 20 0 30 10
             37
             38
             39----樣例輸出：
             40
             413.536
             42-15.000
             43
             44
             45----分析：
             46
             47二分答案，計(jì)算面積。
             48
             49*/
             50
             51
             52#include <iostream>
             53#include <cstdio>
             54#include <cmath>
             55#include <iomanip>
             56#include <algorithm>
             57
             58using namespace std;
             59
             60
             61template<class T, unsigned int N>
             62class  Con
             63{
             64public : 
             65        void input() {
             66                int i;
             67                cin >> this->n;
             68                for ( i = 0; i < this->n; ++i ) {
             69                        cin >> this->x[ i ] >> this->y[ i ];
             70                }
             71                this->top = min( this->y[ 0 ], this->y[ n - 1 ] );
             72                for ( i = 1; (i < this->n) && (this->y[ i - 1 ] > this->y[ i ]); ++i ) {
             73                }
             74                this->c = i - 1;
             75                this->bottom = this->y[ this->c ];
             76        }
             77
             78        double cross( double x0, double y0, double x1, double y1 ) const {
             79                return x0 * y1 - x1 * y0;
             80        }
             81
             82        double area( double level ) const {
             83                if ( this->bottom >= level ) {
             84                        return 0;
             85                }
             86                if ( this->top <= level ) {
             87                        level = this->top;
             88                }
             89                double yn = level;
             90                int i;
             91
             92                for ( i = 1; (i <= this->c) && (this->y[ i ] >= yn); ++i ) {
             93                }
             94                int lei = i;
             95                double le = (this->y[ i-1 ] - yn) * (this->x[ i ] - this->x[ i-1 ]) / 
             96                        (this->y[ i-1 ] - this->y[ i ]) + this->x[ i-1 ];
             97
             98                for ( i = this->c + 1; (i < this->n) && (this->y[ i ] < yn); ++i ) {
             99                }
            100                int rii = i - 1;
            101                double ri = this->x[ i ] - 
            102                        (this->y[ i ] - yn) * (this->x[ i ] - this->x[ i-1 ]) / 
            103                        (this->y[ i ] - this->y[ i-1 ]);
            104
            105                double area2 = 0;
            106                for ( i = lei; i < this->c; ++i ) {
            107                        area2 += cross( this->x[ i+1 ] - le, this->y[ i+1 ] - yn, 
            108                                this->x[ i ] - le, this->y[ i ] - yn );
            109                }
            110                for ( i = rii; i > this->c; --i ) {
            111                        area2 += cross( this->x[ i ] - ri, this->y[ i ] - yn, 
            112                                this->x[ i-1 ] - ri, this->y[ i-1 ] - yn );
            113                }
            114                return ( (ri - le) * (yn - this->bottom) - area2 ) / 2;
            115        }
            116
            117        T  getBottom() const {
            118                return this->bottom;
            119        }
            120        T  getTop() const{
            121                return this->top;
            122        }
            123
            124private : 
            125        int n, c;
            126        T   x[ N ], y[ N ], bottom, top;
            127}            ;
            128
            129
            130const int N = 1009;
            131const double EPS = 0.0001;
            132
            133Con<int, N> p, q;
            134int a;
            135
            136double solve() {
            137        double hig = min( p.getTop(),    q.getTop()    );
            138        double low = min( p.getBottom(), q.getBottom() );
            139        double mid;
            140        while ( hig - low > EPS ) {
            141                mid = (hig + low) / 2;
            142                if ( p.area(mid) + q.area(mid) < a ) {
            143                        low = mid;
            144                }
            145                else {
            146                        hig = mid;
            147                }
            148        }
            149        return hig;
            150}
            151
            152int main() {
            153        int t;
            154        cin >> t;
            155        while ( 0 < t-- ) {
            156                cin >> a;
            157                p.input();
            158                q.input();
            159                cout << fixed << setprecision(3) << solve() << endl;
            160        }
            161        return 0;
            162}
            163
            
		
            
			posted on 2012-05-13 22:54 coreBugZJ 閱讀(818) 評(píng)論(0)  編輯 收藏 引用  所屬分類: ACM 、Algorithm 、課內(nèi)作業(yè) 
		
            
	
            
	
	





            
	    
    




            






            

				

            


    
    







            
	   
	



无码国内精品久久人妻麻豆按摩|
久久无码人妻一区二区三区午夜|
欧美一区二区三区久久综合
|
粉嫩小泬无遮挡久久久久久|
国产精品日韩欧美久久综合|
久久久久久久波多野结衣高潮|
久久久国产精品网站|
狠狠色噜噜色狠狠狠综合久久|
久久www免费人成看国产片
|
精品久久久无码中文字幕|
色综合久久久久综合99|
99久久夜色精品国产网站|
中文字幕一区二区三区久久网站|
亚洲精品乱码久久久久久|
国产精品久久久久免费a∨|
精品久久久久久国产三级|
久久久国产精华液|
91久久精品电影|
韩国免费A级毛片久久|
久久综合鬼色88久久精品综合自在自线噜噜|
久久综合狠狠色综合伊人|
热99RE久久精品这里都是精品免费|
国产欧美久久一区二区|
94久久国产乱子伦精品免费|
亚洲国产精品成人久久|
久久99热这里只有精品66|
国内精品伊人久久久久影院对白|
999久久久无码国产精品|
亚洲国产成人久久综合碰碰动漫3d|
伊人久久大香线蕉av一区|
亚洲国产成人久久综合野外|
久久综合久久美利坚合众国|
久久精品无码专区免费|
久久亚洲中文字幕精品一区|
久久午夜综合久久|
伊人久久精品无码二区麻豆|
噜噜噜色噜噜噜久久|
久久AV高潮AV无码AV|
亚洲va中文字幕无码久久|
久久九九精品99国产精品|
久久91精品综合国产首页|