• <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>
            二分水面高度,然后求總水量(就是求多邊形面積)

            /*************************************************************************
            Author: WHU_GCC
            Created Time: 2007-8-10 13:49:09
            File Name: pku3334.cpp
            Description: 
            ***********************************************************************
            */

            #include 
            <algorithm>
            #include 
            <iostream>
            #include 
            <sstream>
            #include 
            <string>
            #include 
            <queue>
            #include 
            <list>
            #include 
            <set>
            #include 
            <map>
            #include 
            <cmath>
            #include 
            <vector>
            #include 
            <cctype>
            #include 
            <cstring>
            using namespace std;
            #define out(x) (cout<<#x<<": "<<x<<endl)
            const int maxint=0x7FFFFFFF;
            const long long maxlonglong=0x7FFFFFFFFFFFFFFFLL;
            const double inf = 1e200;
            const double eps = 1e-9;
            template
            <class T>void show(T a, int n){for(int i=0; i<n; ++i) cout<<a[i]<<' '; cout<<endl;}
            template
            <class T>void show(T a, int r, int l){for(int i=0; i<r; ++i)show(a[i],l);cout<<endl;}

            const int maxn = 2000;

            typedef 
            struct
            {
                
            double x, y;
            }
             point_t;

            point_t ga[maxn], gb[maxn];
            int cnt_ga, cnt_gb;
            int bottom_a, bottom_b;
            int v_water;

            point_t p[maxn];
            int cnt_p;

            double cross(point_t a, point_t b)
            {
                
            return a.x * b.y - a.y * b.x;
            }


            double count_area()
            {
                
            double ret = 0.0;
                
            for (int i = 0; i < cnt_p; i++)
                
            {
                    ret 
            += cross(p[i], p[(i + 1% cnt_p]) / 2.0;
                }

                
            return ret;
            }


            bool ok(double h)
            {
                
            double area = 0.0;
                cnt_p 
            = 0;
                
            for (int i = 0; i < bottom_a; i++)
                
            {
                    
            if (cnt_p > 0)
                    
            {
                        p[cnt_p] 
            = ga[i];
                        cnt_p
            ++;
                    }

                    
            if (ga[i].y >= h && ga[i + 1].y < h)
                    
            {
                        
            double t = (ga[i].y - h) / (h - ga[i + 1].y);
                        
            double x = (ga[i].x + t * ga[i + 1].x) / (t + 1);
                        p[
            0].x = x;
                        p[
            0].y = h;
                        cnt_p
            ++;
                    }

                }

                
            for (int i = bottom_a; i < cnt_ga; i++)
                
            {
                    
            if (cnt_p > 0)
                    
            {
                        p[cnt_p] 
            = ga[i];
                        cnt_p
            ++;
                    }

                    
            if (ga[i].y < h && ga[i + 1].y >= h)
                    
            {
                        
            double t = (ga[i].y - h) / (h - ga[i + 1].y);
                        
            double x = (ga[i].x + t * ga[i + 1].x) / (t + 1);
                        p[cnt_p].x 
            = x;
                        p[cnt_p].y 
            = h;
                        cnt_p
            ++;
                        
            break;
                    }

                }

                area 
            += count_area();
                cnt_p 
            = 0;
                
            for (int i = 0; i < bottom_b; i++)
                
            {
                    
            if (cnt_p > 0)
                    
            {
                        p[cnt_p] 
            = gb[i];
                        cnt_p
            ++;
                    }
                    
                    
            if (gb[i].y >= h && gb[i + 1].y < h)
                    
            {
                        
            double t = (gb[i].y - h) / (h - gb[i + 1].y);
                        
            double x = (gb[i].x + t * gb[i + 1].x) / (t + 1);
                        p[
            0].x = x;
                        p[
            0].y = h;
                        cnt_p
            ++;
                    }

                }

                
            for (int i = bottom_b; i < cnt_gb; i++)
                
            {
                    
            if (cnt_p > 0)
                    
            {
                        p[cnt_p] 
            = gb[i];
                        cnt_p
            ++;
                    }

                    
            if (gb[i].y < h && gb[i + 1].y >= h)
                    
            {
                        
            double t = (gb[i].y - h) / (h - gb[i + 1].y);
                        
            double x = (gb[i].x + t * gb[i + 1].x) / (t + 1);
                        p[cnt_p].x 
            = x;
                        p[cnt_p].y 
            = h;
                        cnt_p
            ++;
                        
            break;
                    }

                }

                area 
            += count_area();
                
            if (area >= v_water) return false;
                
            else return true;
            }



            double work()
            {
                
            double up, down;
                up 
            = min(min(ga[0].y, ga[cnt_ga - 1].y), min(gb[0].y, gb[cnt_gb - 1].y));
                
            double t1 = inf, t2 = inf;
                
            for (int i = 0; i < cnt_ga; i++if (ga[i].y < t1)
                
            {
                    t1 
            = ga[i].y;
                    bottom_a 
            = i;
                }

                
            for (int i = 0; i < cnt_gb; i++if (gb[i].y < t2)
                
            {
                    t2 
            = gb[i].y;
                    bottom_b 
            = i;
                }

                down 
            = min(t1, t2);
                
                
            while (fabs(up - down) > eps)
                
            {
                    
            double mid = (up + down) / 2.0;
                    
            if (ok(mid))
                        down 
            = mid;
                    
            else up = mid;
                }

                
            return up;
            }


            int main()
            {
                
            int ca;
                
            for (scanf("%d"&ca); ca--;)
                
            {
                    scanf(
            "%d"&v_water);
                    scanf(
            "%d"&cnt_ga);
                    
            for (int i = 0; i < cnt_ga; i++) scanf("%lf%lf"&ga[i].x, &ga[i].y);
                    scanf(
            "%d"&cnt_gb);
                    
            for (int i = 0; i < cnt_gb; i++) scanf("%lf%lf"&gb[i].x, &gb[i].y);
                    
            double ans = work();
                    printf(
            "%.3lf\n", ans);
                }

                
            return 0;
            }
            posted on 2007-08-15 08:59 Felicia 閱讀(463) 評論(1)  編輯 收藏 引用 所屬分類: 計算幾何
            Comments
            • # re: [計算幾何]pku3334
              babt
              Posted @ 2011-05-14 15:42
              代碼有點小問題。
              這組數(shù)據(jù)過不去。
              31
              6
              -45 23 -40 22 -30 20 -20 19 -10 18 -5 22
              6
              0 22 10 21 20 20 30 19 40 20 42 22
              應(yīng)該是19.964  回復(fù)  更多評論   
             
            狠狠综合久久综合88亚洲| 久久精品成人一区二区三区| 亚洲国产精品无码久久SM| 亚洲第一极品精品无码久久| 久久综合给合久久狠狠狠97色69| 日日躁夜夜躁狠狠久久AV| 亚洲精品高清久久| 久久久久久久97| 国产AV影片久久久久久| 亚洲日本va午夜中文字幕久久 | 久久国产精品成人片免费| 伊人久久大香线蕉精品| 欧美精品国产综合久久| 亚洲精品高清国产一久久| 一本久久a久久精品亚洲| 久久精品国产99久久香蕉| 中文字幕久久久久人妻| 久久久久久av无码免费看大片| 亚洲AV无码久久精品色欲| 久久精品国产一区二区三区不卡 | 久久精品免费一区二区| 99久久精品久久久久久清纯| 青草国产精品久久久久久| 一级做a爰片久久毛片免费陪| 亚洲国产精品婷婷久久| 无码精品久久久天天影视| 狠狠色丁香久久婷婷综合蜜芽五月| 国产福利电影一区二区三区久久老子无码午夜伦不 | 久久人人妻人人爽人人爽| 久久青青草原精品国产不卡| 久久国产精品久久精品国产| AV无码久久久久不卡蜜桃| 欧美麻豆久久久久久中文| 一本伊大人香蕉久久网手机| 久久综合九色综合精品| 国产成人无码久久久精品一| 久久久久免费看成人影片| 久久亚洲精品国产精品| 无码AV波多野结衣久久| 亚洲精品美女久久777777| 97久久国产综合精品女不卡|