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

            Why so serious? --[NKU]schindlerlee

            pku2074 線段的切割

            挺好的一道計算幾何題目
            題目大意是:給一條線段代表房子,給一條線段代表路,給一些障礙物,求在路上能完全看到房子的最長連續長度
            題目中所有線段都是和x軸平行的
            兩個難點
            1、利用相似三角形,求出再房子和障礙物連線在路上的交點

            2、判斷線段的相交方式,并切割線段

            這些問題都解決了之后,就是寫代碼了
              1 /* 
              2  * SOUR:pku 2074
              3  * ALGO:computional geometry
              4  * DATE: Thu, 15 Oct 2009 23:22:48 +0800
              5  * COMM:3
              6  * */
              7 #include<iostream>
              8 #include<cstdio>
              9 #include<cstdlib>
             10 #include<cstring>
             11 #include<algorithm>
             12 #include<vector>
             13 #include<cassert>
             14 #include<cmath>
             15 using namespace std;
             16 typedef long long LL;
             17 const int maxint = 0x7fffffff;
             18 const long long max64 = 0x7fffffffffffffffll;
             19 template<class T>void show(T a, int n){for(int i=0;i<n;++i)cout<<a[i]<<' ';cout<<endl;}
             20 template<class T>void show(T a,int r,int l){for(int i=0;i<r;++i)show(a[i],l);cout<<endl;}
             21 #define pr(x) fprintf(stderr, x)
             22 /* #define pr(x) for(;0;) */
             23 const int N = 512;
             24 const double eps = 1e-7;
             25 struct NODE {
             26     double x1,x2,y;
             27     NODE(){}
             28     NODE(double a,double b){ x1 = a,x2 = b; }
             29 }h,ob,root;
             30 vector<NODE> g[N];
             31 int n,top,pt;
             32 
             33 
             34 struct point_t{
             35     double x,y;
             36     point_t(){}
             37     point_t(double a,double b){
             38         x = a,y = b;
             39     }
             40 };
             41 point_t operator +(point_t a,point_t b) { return point_t(a.x + b.x,a.y + b.y); }
             42 point_t operator -(point_t a,point_t b) { return point_t(a.x - b.x,a.y - b.y); }
             43 point_t operator *(point_t a,double b) { return point_t(a.x * b,a.y * b); }
             44 point_t operator /(point_t a,double b) { return point_t(a.x / b,a.y / b); }
             45 double sqr(double x) {return x * x;}
             46 double dist(point_t a) { return sqrt(sqr(a.x) + sqr(a.y)); }
             47 double dist(point_t a,point_t b) { return dist(a-b); }
             48 
             49 void cut(int idx,double v1,double v2)
             50 {
             51     int i,j,k;
             52     for(i = 0;i < g[idx-1].size();i++) {
             53         if(v1 <= g[idx-1][i].x1 && v2 >= g[idx-1][i].x2) {
             54         }else if(v1 <= g[idx-1][i].x1 && v2 > g[idx-1][i].x1 && v2 <= g[idx-1][i].x2) {
             55             g[idx].push_back(NODE(v2,g[idx-1][i].x2));
             56         }else if(v1 >= g[idx-1][i].x1 && v1 < g[idx-1][i].x2 && v2 >= g[idx-1][i].x2) {
             57             g[idx].push_back(NODE(g[idx-1][i].x1,v1));
             58         }else if(v1 >= g[idx-1][i].x1 && v2 <= g[idx-1][i].x2) {
             59             g[idx].push_back(NODE(g[idx-1][i].x1,v1));
             60             g[idx].push_back(NODE(v2,g[idx-1][i].x2));
             61         }else {
             62             g[idx].push_back(g[idx-1][i]);
             63         }
             64     }
             65 }
             66 
             67 
             68 point_t cacu(point_t a,point_t b)
             69     //b為ob,a為h
             70 {
             71     assert(h.y - root.y >= 0);
             72     assert(h.y - ob.y >= 0);
             73     return a + (b - a) * (h.y - root.y) / (h.y - ob.y);
             74 }
             75 
             76 int main()
             77 {
             78     int i,j,k;
             79     while(scanf("%lf%lf%lf",&h.x1,&h.x2,&h.y) && (h.x1 || h.x2 || h.y)) {
             80         scanf("%lf%lf%lf",&root.x1,&root.x2,&root.y);
             81         scanf("%d",&n);
             82         for(i = 0;i < N;i++) {
             83             g[i].clear();
             84         }
             85         g[0].push_back(root);
             86         for(i = 1,j = 0;i <= n;i++) {
             87             scanf("%lf%lf%lf",&ob.x1,&ob.x2,&ob.y);
             88             if(ob.y < h.y && ob.y > root.y) {
             89                 point_t v1 = cacu(point_t(h.x2,h.y) , point_t(ob.x1,ob.y));
             90                 point_t v2 = cacu(point_t(h.x1,h.y) , point_t(ob.x2,ob.y));
             91                 //printf("<%f,%f> <%f,%f>\n",v1.x,v1.y,v2.x,v2.y);
             92                 assert(v1.x <= v2.x && fabs(v1.y - v2.y) < eps);
             93                 cut(++j,v1.x,v2.x);
             94             }
             95         }
             96         double res = 0;
             97         for(i = 0;i < g[j].size();i++) {
             98             res = max(res,g[j][i].x2 - g[j][i].x1);
             99         }
            100         if(res < eps) {
            101             printf("No View\n");
            102         }else {
            103             printf("%.2f\n",res);
            104         }
            105     }
            106     return 0;
            107 }
            108 
            109 
            1Y感覺很不錯

            posted on 2009-10-16 14:43 schindlerlee 閱讀(1154) 評論(0)  編輯 收藏 引用 所屬分類: 解題報告

            久久精品aⅴ无码中文字字幕不卡 久久精品成人欧美大片 | 久久久国产精品| 中文成人久久久久影院免费观看| 午夜精品久久久久久久无码| 久久精品黄AA片一区二区三区| 91精品国产综合久久四虎久久无码一级| 久久久久无码国产精品不卡| 久久久精品2019免费观看| 久久精品国产亚洲7777| 日日噜噜夜夜狠狠久久丁香五月| 国产巨作麻豆欧美亚洲综合久久| 久久中文字幕人妻熟av女| 99久久精品九九亚洲精品| 中文国产成人精品久久不卡| 精品久久久久久无码中文字幕| 久久人爽人人爽人人片AV| 婷婷久久精品国产| 66精品综合久久久久久久| 精品久久久无码人妻中文字幕豆芽| 色婷婷久久综合中文久久一本| 久久99国产精品久久99果冻传媒| 久久伊人五月丁香狠狠色| 久久久久亚洲精品中文字幕| 久久久久久免费一区二区三区| 久久综合久久自在自线精品自| 一级女性全黄久久生活片免费 | 亚洲精品无码久久千人斩| 久久综合伊人77777| 精品国产一区二区三区久久蜜臀| 久久精品国产91久久麻豆自制| 日产精品99久久久久久| 狠狠色噜噜色狠狠狠综合久久| 香蕉久久夜色精品国产2020| 久久久精品国产Sm最大网站| 精品欧美一区二区三区久久久| 久久精品国产久精国产| 国产午夜精品理论片久久影视| 激情伊人五月天久久综合| 亚洲色欲久久久综合网| 久久久国产乱子伦精品作者 | 天堂无码久久综合东京热|