• <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 線段的切割

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

            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感覺很不錯(cuò)

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

            日本精品久久久中文字幕 | 亚洲国产成人久久综合碰| 亚洲伊人久久精品影院| 女同久久| 久久午夜综合久久| 国内精品免费久久影院| 久久久精品一区二区三区| 国产午夜精品久久久久免费视| 久久99精品久久久大学生| 亚洲日本va午夜中文字幕久久 | 亚洲综合精品香蕉久久网97| 久久九九精品99国产精品| 久久精品aⅴ无码中文字字幕不卡 久久精品aⅴ无码中文字字幕重口 | 狠色狠色狠狠色综合久久| 久久久久亚洲精品无码蜜桃 | 奇米影视7777久久精品| 日韩人妻无码精品久久久不卡| 777午夜精品久久av蜜臀| 日日噜噜夜夜狠狠久久丁香五月| 亚洲色婷婷综合久久| 香蕉久久夜色精品升级完成 | 99久久99这里只有免费费精品| 日韩人妻无码一区二区三区久久 | 午夜视频久久久久一区 | 久久精品亚洲欧美日韩久久| 久久久久久亚洲精品不卡| 少妇久久久久久被弄到高潮| 久久人人爽人人爽人人片AV东京热| 久久亚洲熟女cc98cm| 精品国产99久久久久久麻豆| 久久久噜噜噜久久熟女AA片| 99久久婷婷国产一区二区| 中文字幕无码久久人妻| 少妇久久久久久被弄高潮| 91亚洲国产成人久久精品网址| 亚洲国产成人精品女人久久久| 亚洲精品乱码久久久久久| 久久免费线看线看| 中文精品99久久国产| www.久久热| 亚洲精品无码久久久久AV麻豆|