博客
关于我
强烈建议你试试无所不能的chatGPT,快点击我
计算几何 点线的综合题, 精度+ 线段相交+ 求交点 + 求面积 poj 2826 An Easy Problem?! (推荐)...
阅读量:6208 次
发布时间:2019-06-21

本文共 9662 字,大约阅读时间需要 32 分钟。

题目来源: http://poj.org/problem?id=2826
这是一道细节题。
题目中让我们用两条线段接雨水,雨水是垂直落下的,问我们用给定的两条线段能接到多少水。
这里用很多种情况都要一一讨论。
1:两条线段不想交的时候接不到雨水  
2:两条线段重合的时候接不到雨水
3:两条线段的交点与期中一条线段的最高点相同时,无法接到雨水
4:有一条线段水平时接不到雨水。
5:当两条线段的最高点均在交点一侧时,期中较高的点遮住了较低的点时,无法接住雨水。
 
注意: 1 这道题不是特别卡精度。 程序中有sig(x) 和 add(a ,b) 处理精度的
2: 这题 我用的 计算面积是等高比, 不出现 -0.00, 故不卡 EPS 
3: 提交时, 一定用 C++ , 不能用 G++ (一直wa)
 
后来重做一遍的代码:
double add(double a, double b){    return (fabs(a +b) < EPS * (fabs(a) + fabs(b))) ? 0 : (a + b) ;}struct Point{    double x, y;    Point(){}    Point(double x, double y):x(x), y(y){}    Point operator -(Point a){        return Point(add(x , -a.x) , add(y , -a.y)) ;    }     Point operator +(Point a){        return Point(add(x , a.x) , add(y , a.y)) ;    }    double operator^(Point a){        return add(x * a.y , -y * a.x) ;    }    Point operator*(double d){        return Point(x * d , y *d) ;    }    bool operator == (Point a){        return (x == a.x) && (y == a.y) ;    }};//判断点p0是否在线段p1p2内bool on_segment(Point p1 ,Point p2, Point p0){    return ((p1 - p0).x * (p2 - p0).x <= 0) && ((p1 - p0).y * (p2 - p0).y <= 0) ;}struct Line{    Point st, ed;    Line(){}    Line(Point s, Point e){        st = s;        ed = e ;    }    bool parallel(Line l){        return ((st - ed)^(l.st - l.ed))== 0 ;    }    bool intersection(Line l){        Point p1 , p2, q1, q2 ;        p1 = st ;        p2 = ed;        q1 = l.st ;        q2 = l.ed ;        double d1 = (p2 - p1)^(q1 - p1) ;        double d2 = (p2 - p1)^(q2 - p1) ;        double d3 = (q2 - q1)^(p1 - q1) ;        double d4 = (q2 - q1)^(p2 - q1) ;        if( (d1 == 0 && on_segment(p1, p2 , q1))         || (d2 == 0 && on_segment(p1, p2 , q2))         || (d3 == 0 && on_segment(q1, q2 , p1))         || (d4 == 0 && on_segment(q1 ,q2 , p2)))           return 1;         if(d1 * d2 < 0 && d3 * d4 < 0)            return 1;        return 0 ;    }    Point intersectpoint(Line l){        double d1 = (l.ed - l.st)^(l.st - st) ;        double d2 = (l.ed - l.st)^(ed - st) ;        return st + (ed - st)*(d1 / d2) ;    }    void read(){        scanf("%lf%lf%lf%lf" , &st.x , &st.y ,&ed.x ,&ed.y) ;    }    void write(){        printf("%lf %lf %lf %lf\n" , st.x ,st.y , ed.x ,ed.y) ;    }};Line l1, l2 ;Point ix;bool Yes(){    if(l1.parallel(l2)) return 0 ; //平行 或重叠    if(!l1.intersection(l2)) return 0 ; // 没有交点    if(l1.st.y == l1.ed.y || l2.st.y == l2.ed.y) //有一条线段平行x轴        return 0 ;    ix = l1.intersectpoint(l2) ;    if(ix == l1.ed || ix == l2.ed) return 0 ;// 交点为某一条线段中y值较大的端点    double d1x = (l1.ed.x - ix.x ) ;    double d2x = (l2.ed.x - ix.x) ;    if(d1x * d2x > 0 ){  // y值较大的端点在交点的同一侧,且一条遮盖另一条线段        double d = (l1.ed - ix)^(l2.ed - ix) ;        if( (d > 0 && l1.ed.x <= l2.ed.x) ||( d < 0 &&  l1.ed.x >= l2.ed.x))            return 0 ;    }    return 1;}int main(){    int t;    scanf("%d", &t);    while(t--){        l1.read() ;        l2.read() ;        if(l1.st.y > l1.ed.y)            swap(l1.st , l1. ed) ;        if(l2.st.y > l2.ed.y)            swap(l2.st , l2. ed) ;        if(Yes()){            double area = 0.0 ;            area = (l1.ed - ix)^(l2.ed - ix) ;            area = area < 0 ? -area : area ;            if(l1.ed.y > l2.ed.y)                swap(l1.ed, l2.ed) ;            double dx = (l1.ed.y - ix.y) / (l2.ed.y - ix.y) ;            printf("%.2lf\n" , area*0.5 * dx  + EPS) ;        }        else puts("0.00") ;    }   return 0 ;}

 

 
无sig(x) 函数的 代码如下:
1 #include 
2 #include
3 #include
4 #include
5 #include
6 #include
7 #include
8 #include
9 #include
10 #include
11 #include
12 #include
13 #include
14 15 using namespace std; 16 double EPS=1e-10; 17 18 // 考虑误差的加法运算 19 double add(double a,double b) 20 { 21 if(fabs(a+b)
0 左转, d1 <0 右转 63 double d2=(p2-p1)^(q2-p1); 64 double d3=(q2-q1)^(p1-q1); 65 double d4=(q2-q1)^(p2-q1); 66 if((d1==0 && on_segment(p1,p2,q1) )|| (d2==0 && on_segment(p1,p2,q2) )|| 67 (d3==0&& on_segment(q1,q2,p1)) || (d4==0 && on_segment(q1,q2,p2))) 68 return 1; 69 else if(d1*d2<0 && d3*d4 <0) // 中间是 && 70 return 1; 71 return 0; 72 } 73 // 判断线段p1p2与线段 q1q2是否重叠 74 int doubleline( Point p1,Point p2, Point q1,Point q2 ) 75 { 76 double d1=(p2-p1)^(q1-p1); // 计算p1p2 到q 点的转向 d1>0 左转, d1 <0 右转 77 double d2=(p2-p1)^(q2-p1); 78 if(d1== 0 && d2== 0 ) 79 return 1; 80 return 0; 81 82 } 83 // 计算直线p1p2与q1q2的交点 84 Point intersectnode(Point p1,Point p2,Point q1,Point q2){ 85 double d1=( (q2-q1)^(q1-p1) ); 86 double d2=( (q2-q1)^(p2-p1) ); 87 return p1+ (p2-p1)*(d1/d2) ; 88 } 89 // 返回 两点中 y 值 较大的点 90 Point ver(Point a,Point b) 91 { 92 return (a.y>=b.y) ? a:b; 93 } 94 95 struct Line{ 96 Point st ; 97 Point ed ; 98 Line(){} 99 Line(Point a , Point b){100 st = a ;101 ed = b ;102 }103 void read(){104 scanf("%lf%lf%lf%lf" , &st.x , &st.y , &ed.x , &ed.y) ;105 }106 void writee()107 {108 printf("line= %lf %lf %lf %lf\n",st.x,st.y,ed.x,ed.y);109 }110 };111 Line l1;112 Line l2;113 114 // 判断 不可行 情况115 int Yes_No()116 {117 if( ! intersection(l1.st , l1.ed , l2.st, l2.ed) ) return 0; // 不相交118 if(doubleline(l1.st , l1.ed , l2.st, l2.ed ) ) return 0; // 相交不重合119 Point sect= intersectnode(l1.st, l1.ed, l2.st, l2.ed); // 有唯一交点120 Point p1=ver(l1.st, l1.ed);121 Point p2=ver(l2.st, l2.ed);122 if(sect == p1 || sect == p2) return 0; // 交点为线段较大y值的端点123 if( ( (l1.st) . y==(l1.ed) .y ) || ( ( l2.st ) .y == ( l2.ed ).y) ) return 0; // 有一条线为平行线124 if( ( sect.x < p1.x) && (sect.x < p2.x) || (sect.x > p1.x) && (sect.x > p2.x ) )125 {126 int d= (p1 - sect) ^ (p2 - sect);127 if( (d >0 && (p1.x <= p2.x) ) || (d < 0 && (p1.x>= p2.x) ) ) return 0; // 当2线段较大y值的端点 都在 交点的一侧, 出现 遮挡现象128 }129 return 1;130 }131 132 int main()133 {134 int t;135 scanf("%d",&t);136 while(t--)137 {138 scanf("%lf%lf%lf%lf",&((l1.st).x ), &((l1.st).y), &((l1.ed).x), & ( (l1.ed).y) );139 scanf("%lf%lf%lf%lf",&((l2.st).x ), &((l2.st).y), & ((l2.ed).x ), & ((l2.ed).y) );140 if(Yes_No() )141 {142 Point sect= intersectnode(l1.st, l1.ed , l2.st, l2.ed );143 Point p1=ver(l1.st, l1.ed);144 Point p2=ver(l2.st, l2.ed);145 if( (p1.y >p2.y ) ) // 让 p1为较大y值得点 ,点可交换146 {147 Point tmp=p1;148 p1=p2;149 p2=tmp;150 }151 double d= fabs ( (p1 - sect) ^ (p2 - sect) ); // 叉乘计算面积, 等高的边长比计算所求面积152 double x= d *( p1.y-sect.y ) / (p2.y - sect.y) ;153 printf("%.2lf\n",x/2.0 ); // 结果 + EPS防止出现-0.00,这个程序可以不加也AC154 }155 else printf("0.00\n");156 }157 }

 

 

有 sig(x)函数的代码如下:

1 #include 
2 #include
3 #include
4 #include
5 #include
6 #include
7 #include
8 #include
9 #include
10 #include
11 #include
12 #include
13 #include
14 15 using namespace std; 16 double EPS=1e-10; 17 int sig(double d) // 符号函数, 用于误差 18 { 19 if(fabs(d) < EPS) return 0; 20 return d>0 ? 1: -1; 21 } 22 // 考虑误差的加法运算 23 double add(double a,double b) 24 { 25 if(fabs(a+b)
0 左转, d1 <0 右转 67 double d2=(p2-p1)^(q2-p1); 68 double d3=(q2-q1)^(p1-q1); 69 double d4=(q2-q1)^(p2-q1); 70 if((d1==0 && on_segment(p1,p2,q1) )|| (d2==0 && on_segment(p1,p2,q2) )|| 71 (d3==0&& on_segment(q1,q2,p1)) || (d4==0 && on_segment(q1,q2,p2))) 72 return 1; 73 else if(d1*d2<0 && d3*d4 <0) // 中间是 && 74 return 1; 75 return 0; 76 } 77 // 判断线段p1p2与线段 q1q2是否重叠 78 int doubleline( Point p1,Point p2, Point q1,Point q2 ) 79 { 80 double d1=(p2-p1)^(q1-p1); // 计算p1p2 到q 点的转向 d1>0 左转, d1 <0 右转 81 double d2=(p2-p1)^(q2-p1); 82 if(d1== 0 && d2== 0 ) 83 return 1; 84 return 0; 85 86 } 87 // 计算直线p1p2与q1q2的交点 88 Point intersectnode(Point p1,Point p2,Point q1,Point q2){ 89 double d1=( (q2-q1)^(q1-p1) ); 90 double d2=( (q2-q1)^(p2-p1) ); 91 return p1+ (p2-p1)*(d1/d2) ; 92 } 93 // 返回 两点中 y 值 较大的点 94 Point ver(Point a,Point b) 95 { 96 return sig(a.y-b.y) >= 0 ? a:b; 97 } 98 99 struct Line{100 Point st ;101 Point ed ;102 Line(){}103 Line(Point a , Point b){104 st = a ;105 ed = b ;106 }107 void read(){108 scanf("%lf%lf%lf%lf" , &st.x , &st.y , &ed.x , &ed.y) ;109 }110 void writee()111 {112 printf("line= %lf %lf %lf %lf\n",st.x,st.y,ed.x,ed.y);113 }114 };115 Line l1;116 Line l2;117 118 // 判断 不可行 情况119 int Yes_No()120 {121 if( ! intersection(l1.st , l1.ed , l2.st, l2.ed) ) return 0; // 不相交122 if(doubleline(l1.st , l1.ed , l2.st, l2.ed ) ) return 0; // 相交不重合123 Point sect= intersectnode(l1.st, l1.ed, l2.st, l2.ed); // 有唯一交点124 Point p1=ver(l1.st, l1.ed);125 Point p2=ver(l2.st, l2.ed);126 if(sect == p1 || sect == p2) return 0; // 交点为线段较大y值的端点127 if( sig( (l1.st) . y- (l1.ed) .y ) ==0 || sig( ( l2.st ) .y - ( l2.ed ).y) == 0 ) return 0; // 有一条线为平行线128 if( ( sig(sect.x - p1.x) < 0 && sig(sect.x - p2.x) < 0 ) || ( sig(sect.x - p1.x) >0 && sig(sect.x - p2.x ) >0 ) )129 {130 int d= (p1 - sect) ^ (p2 - sect);131 if( (d >0 && (p1.x - p2.x) <=0 ) || (d < 0 && sig(p1.x- p2.x) >=0 ) ) return 0; // 当2线段较大y值的端点a,b 都在 交点的一侧, 出现 a,b遮挡现象132 }133 return 1;134 }135 136 int main()137 {138 int t;139 scanf("%d",&t);140 while(t--)141 {142 scanf("%lf%lf%lf%lf",&((l1.st).x ), &((l1.st).y), &((l1.ed).x), & ( (l1.ed).y) );143 scanf("%lf%lf%lf%lf",&((l2.st).x ), &((l2.st).y), & ((l2.ed).x ), & ((l2.ed).y) );144 if(Yes_No() )145 {146 Point sect= intersectnode(l1.st, l1.ed , l2.st, l2.ed );147 Point p1=ver(l1.st, l1.ed);148 Point p2=ver(l2.st, l2.ed);149 if( sig(p1.y -p2.y ) >0 ) // 让 p1为较大y值得点 ,点可交换150 {151 Point tmp=p1;152 p1=p2;153 p2=tmp;154 }155 double d= fabs ( (p1 - sect) ^ (p2 - sect) ); // 叉乘计算面积, 等高的边长比计算所求面积156 double x= d *( p1.y-sect.y ) / (p2.y - sect.y) ;157 printf("%.2lf\n",x/2.0 ); // 结果 + EPS防止出现-0.00,这个程序可以不加也AC158 }159 else printf("0.00\n");160 }161 }

 

转载于:https://www.cnblogs.com/zn505119020/p/3630173.html

你可能感兴趣的文章
四:DRF项目开发的准备
查看>>
Linux 进程管理
查看>>
【和孩子一起学编程】 python笔记--第五天
查看>>
java处理高并发高负载类网站的优化方法
查看>>
SpringMVC调用过程
查看>>
memcached(十一)magent实现高可用
查看>>
关于一个类中方法调用情况
查看>>
使用Allure+testNG自动生成漂亮强大的测试用例报告
查看>>
C/C++求余运算符
查看>>
github地址
查看>>
[改善Java代码]警惕自增的陷阱
查看>>
[改善Java代码]不要随便设置随机种子
查看>>
解决FFmpeg丢失视频流及帧率过高的问题
查看>>
使用java实现MD5、BASE64、RSA的方法
查看>>
树莓派安装omv
查看>>
第六次作业(团队作业)
查看>>
JavaScript中的this陷阱的最全收集--没有之一
查看>>
java中的构造方法
查看>>
一道关于位数扩充的题目
查看>>
[GeekBand] STL vector 查找拷贝操作效率分析
查看>>