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

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>
            亚洲欧美激情视频| 在线一区二区日韩| 麻豆成人在线观看| 亚洲大片一区二区三区| 欧美国产精品| 欧美连裤袜在线视频| 一区二区三区www| 在线亚洲一区二区| 国产主播一区二区三区| 六月婷婷一区| 欧美激情视频给我| 欧美一区二区免费| 久久午夜影视| 亚洲图片欧洲图片av| 性感少妇一区| 在线观看中文字幕亚洲| 日韩网站免费观看| 国产一区二区三区高清| 亚洲国产精彩中文乱码av在线播放| 欧美成人黑人xx视频免费观看| 一区二区三区日韩在线观看| 亚洲欧美综合| 亚洲精品自在久久| 亚洲欧美一级二级三级| 亚洲激情午夜| 亚洲男人的天堂在线aⅴ视频| 在线观看亚洲视频| 中文在线一区| 亚洲二区视频| 香蕉国产精品偷在线观看不卡| 亚洲精品一二三区| 久久国产精品99国产精| 亚洲欧美成人一区二区在线电影 | 亚洲深夜福利网站| 久久国产精品99久久久久久老狼| 一区二区毛片| 久久网站免费| 欧美一区激情| 欧美日韩免费网站| 欧美激情欧美激情在线五月| 国产日韩亚洲欧美| 宅男噜噜噜66一区二区| 亚洲乱码国产乱码精品精天堂| 午夜精品久久久久久久久| 一区二区三区久久久| 麻豆91精品| 麻豆成人91精品二区三区| 国产欧美日韩免费| 一卡二卡3卡四卡高清精品视频| 亚洲区一区二| 葵司免费一区二区三区四区五区| 久久国内精品自在自线400部| 国产精品扒开腿做爽爽爽视频| 亚洲国产欧美在线人成| 在线日韩av| 久久免费精品视频| 久久亚洲一区二区三区四区| 国产午夜亚洲精品不卡| 亚洲免费网站| 欧美一区国产一区| 国产亚洲观看| 久久精品免费观看| 久久亚洲精品视频| 怡红院精品视频| 久久一区二区三区av| 免费的成人av| 亚洲第一综合天堂另类专| 麻豆精品视频在线观看| 欧美激情片在线观看| 夜夜狂射影院欧美极品| 欧美日韩国产精品| 一区二区三区国产精品| 99国产精品一区| 亚洲乱码国产乱码精品精98午夜| 亚洲高清成人| 欧美亚洲视频在线看网址| 亚洲国产合集| 亚洲综合色自拍一区| 亚洲午夜91| 久久激情一区| 曰本成人黄色| 欧美a级大片| 亚洲国内高清视频| 亚洲一区二区久久| 国产精品视频| 久久全国免费视频| 亚洲理论在线观看| 久久国产主播| 亚洲理伦在线| 国产精品v片在线观看不卡 | 亚洲日本欧美天堂| 欧美日韩国产色视频| 国产精品午夜国产小视频| 尤物视频一区二区| 国内外成人在线| 免费在线看一区| 夜夜嗨av一区二区三区网站四季av | 中日韩高清电影网| 久久国产精品久久久| 亚洲国产cao| 欧美日在线观看| 久久国产一区二区| 亚洲伦理中文字幕| 麻豆国产精品va在线观看不卡| 亚洲国产精品一区二区尤物区| 欧美三级视频在线播放| 久久黄色网页| av不卡在线| 欧美国内亚洲| 欧美在线亚洲一区| 在线视频精品一| 久久只有精品| 亚洲精品日本| 久久精品理论片| 欧美一区二区女人| 欧美成人性网| 欧美亚洲免费电影| 亚洲美女性视频| 韩曰欧美视频免费观看| 欧美午夜精品久久久久久人妖 | 欧美sm重口味系列视频在线观看| 亚洲性av在线| 91久久久久久| 悠悠资源网久久精品| 国产精品视频最多的网站| 欧美另类变人与禽xxxxx| 久久久久久97三级| 香蕉久久夜色精品国产| 亚洲一区二区免费| 夜夜躁日日躁狠狠久久88av| 亚洲国产导航| 久久久噜噜噜久久中文字免| 国产亚洲一区二区在线观看 | 欧美成人免费一级人片100| 欧美69视频| 午夜精品久久久久久久99黑人| 日韩视频一区二区三区在线播放免费观看 | 国产精品成人aaaaa网站| 免费亚洲视频| 久久久久久久久久久久久9999| 欧美一级视频精品观看| 午夜影院日韩| 香蕉久久夜色精品| 欧美在线视频观看| 欧美在线观看视频一区二区| 亚洲欧美日韩在线| 午夜亚洲视频| 久久精品国产综合| 在线观看亚洲| 欧美在线一区二区三区| 99亚洲伊人久久精品影院红桃| 国产精品免费看片| 欧美ab在线视频| 激情文学一区| 在线成人激情| 亚洲激情图片小说视频| 亚洲国产欧美日韩| 亚洲人成绝费网站色www| 亚洲精品乱码久久久久久日本蜜臀| 亚洲精品欧美精品| 中文在线资源观看网站视频免费不卡| 亚洲一区二区欧美日韩| 久久se精品一区二区| 免费短视频成人日韩| 亚洲日本中文字幕免费在线不卡| 亚洲免费av观看| 亚洲欧美中文在线视频| 麻豆精品视频在线观看| 欧美日韩调教| 国产一级久久| av不卡在线| 久久久国产精品一区| 国产农村妇女毛片精品久久麻豆| 久久av资源网站| 亚洲精品国久久99热| 久久精品最新地址| 久久久久九九九| 91久久精品视频| 国产综合色在线| 99re热这里只有精品免费视频| 亚洲一区三区电影在线观看| 久久综合色8888| 一区二区三区导航| 久久影院午夜论| 欧美视频在线一区| 亚洲第一页在线| 午夜精品福利视频| 亚洲国产另类精品专区| 欧美一级夜夜爽| 欧美另类极品videosbest最新版本| 国产精品日韩专区| 亚洲精品国精品久久99热一| 久久精品水蜜桃av综合天堂| 亚洲日本视频| 久久蜜桃资源一区二区老牛 | 欧美成人一区二区| 欧美1区2区视频| a91a精品视频在线观看| 快播亚洲色图| 亚洲欧美日韩在线|