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

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二分答案,計算面積。
 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->= 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->+ 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 閱讀(835) 評論(0)  編輯 收藏 引用 所屬分類: ACMAlgorithm課內作業

青青草原综合久久大伊人导航_色综合久久天天综合_日日噜噜夜夜狠狠久久丁香五月_热久久这里只有精品
  • <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页| 亚洲综合精品四区| 欧美一区二区在线免费播放| 黄色综合网站| 亚洲精品乱码视频| 国产精品视频内| 免费国产一区二区| 欧美日韩一区二区三区在线| 午夜精品视频| 久久综合婷婷| 亚洲欧美激情诱惑| 久久亚洲私人国产精品va媚药| 亚洲国产影院| 亚洲欧美在线免费| 亚洲日本一区二区三区| 亚洲制服少妇| 亚洲日韩成人| 欧美专区在线播放| 中文日韩在线视频| 久久福利电影| 午夜日本精品| 欧美大秀在线观看| 久久精品动漫| 欧美日韩国产成人| 麻豆精品视频| 国产精品网站在线观看| 亚洲黄色毛片| 一区二区三区在线观看视频| 一区二区三区导航| 99这里只有久久精品视频| 在线不卡中文字幕播放| 国产精品99久久久久久www| 亚洲国产视频一区| 欧美在线视频导航| 午夜精品电影| 欧美日韩天堂| 亚洲茄子视频| 亚洲欧洲美洲综合色网| 久久久久国产精品午夜一区| 亚洲一区一卡| 欧美日韩一区综合| 亚洲三级国产| 99av国产精品欲麻豆| 久久先锋资源| 蜜桃av久久久亚洲精品| 国产一区二区三区不卡在线观看| 一区二区高清视频| 亚洲调教视频在线观看| 欧美精品18| 亚洲美女在线国产| 一区二区精品在线| 欧美日韩一区在线| 日韩亚洲在线观看| 亚洲婷婷综合色高清在线 | 久久午夜视频| 国内精品福利| 久久精品欧美日韩精品| 久久综合99re88久久爱| 精品成人在线| 久久久噜噜噜久久| 欧美电影免费观看高清完整版| 一区二区三区在线高清| 久久综合伊人77777| 欧美国产第二页| 99这里只有精品| 欧美三级网页| 欧美一二区视频| 欧美成人蜜桃| 中国av一区| 国产伦精品一区二区三区在线观看 | 狠狠色综合网| 免费久久99精品国产自在现线| 亚洲风情在线资源站| 亚洲免费播放| 国产精品女主播| 久久精品女人| 日韩一级免费| 久久精品久久综合| 亚洲人成在线播放网站岛国| 欧美日韩国产黄| 午夜亚洲影视| 欧美国产一区在线| 亚洲欧美国产另类| 一区在线影院| 欧美日韩黄视频| 午夜伦理片一区| 亚洲国产成人不卡| 欧美一区二区三区男人的天堂| 在线成人黄色| 欧美日精品一区视频| 久久精品国产欧美亚洲人人爽 | 亚洲四色影视在线观看| 国产午夜精品一区二区三区视频 | 亚洲一区综合| 欧美激情一区二区三区全黄| 亚洲小视频在线| 在线观看日韩欧美| 国产精品亚洲综合一区在线观看| 久久免费国产精品1| 国产精品99久久久久久久vr| 蜜月aⅴ免费一区二区三区| 亚洲天堂免费观看| 亚洲国产欧美一区二区三区丁香婷| 国产精品高潮视频| 美女精品一区| 欧美淫片网站| 亚洲综合欧美| 夜夜嗨av一区二区三区| 欧美激情精品久久久六区热门| 欧美亚洲视频一区二区| 99国产精品国产精品久久| 精品动漫3d一区二区三区免费版 | 欧美成人资源网| 欧美在线一二三区| 亚洲欧美在线播放| 亚洲男女毛片无遮挡| 99精品国产热久久91蜜凸| 亚洲国产高清在线观看视频| 久久精品亚洲精品| 欧美一区二区三区在线播放| 在线亚洲欧美| 亚洲作爱视频| 日韩视频―中文字幕| 91久久夜色精品国产九色| 激情成人综合网| 国产一级一区二区| 国产日韩欧美麻豆| 国产麻豆91精品| 国产免费观看久久| 国产欧美综合在线| 国产视频久久久久久久| 国产精品视频| 国产日韩亚洲欧美综合| 国产欧美一区二区三区视频| 国产精品日韩欧美综合| 国产精品男女猛烈高潮激情 | 久久久久久久尹人综合网亚洲| 欧美在线观看日本一区| 欧美在线观看一区| 久久久99爱| 美女国产一区| 欧美精彩视频一区二区三区| 欧美区日韩区| 国产精品国产三级国产专播精品人| 欧美日韩一区二区三区在线看 | 日韩一级在线观看| 在线亚洲电影| 久久国产日韩| 欧美gay视频| 亚洲第一视频| 亚洲美女黄色片| 亚洲一区黄色| 久久精品国产99国产精品| 久久综合狠狠综合久久综青草| 欧美成人精品高清在线播放| 欧美日韩亚洲国产精品| 国产精品一区二区你懂得| 韩国欧美国产1区| 久久精品免视看| 欧美不卡视频一区发布| 欧美小视频在线| 激情久久五月| 制服丝袜激情欧洲亚洲| 欧美一级专区免费大片| 欧美成人精品福利| 中文国产成人精品| 久久久91精品| 国产精品白丝av嫩草影院| 国产在线一区二区三区四区| 亚洲激情在线观看视频免费| 亚洲一区二区三区乱码aⅴ| 久久国产夜色精品鲁鲁99| 亚洲二区免费| 午夜在线一区二区| 欧美日本韩国在线| 激情文学综合丁香| 亚洲在线一区二区三区| 欧美成人激情视频| 亚洲欧美成人在线| 欧美另类人妖| 在线国产精品一区| 新67194成人永久网站| 亚洲人体1000| 久久女同精品一区二区| 国产精品一区二区三区免费观看| 亚洲国产美国国产综合一区二区| 午夜亚洲福利| 亚洲精品资源| 欧美第一黄网免费网站| 娇妻被交换粗又大又硬视频欧美| 小处雏高清一区二区三区| 亚洲美女性视频| 欧美片在线观看|