计算几何点线的综合题，精度+ 线段相交+ 求交点 + 求面积 poj 2826 An Easy Problem?! (推荐)

题目来源： 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
" , 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
" , area*0.5 * dx  + EPS) ;
        }
        else puts("0.00") ;
    }
   return 0 ;
}

无sig(x) 函数的代码如下：

  1 #include <iostream>
  2 #include <algorithm>
  3 #include <stdlib.h>
  4 #include <iostream>
  5 #include <stdio.h>
  6 #include <string>
  7 #include <string.h>
  8 #include <vector>
  9 #include <set>
 10 #include <math.h>
 11 #include <cmath>
 12 #include <map>
 13 #include <queue>
 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)<EPS*(fabs(a)+fabs(b))) return 0;
 22     return a+b;
 23 }
 24 struct Point{
 25     double x,y;
 26     Point(){}
 27     Point(double x,double y):x(x),y(y){} // 构造函数，方便代码编写
 28     Point operator +(Point p){
 29         return Point(add(x,p.x), add(y,p.y));
 30     }
 31     Point operator-(Point p){
 32         return Point(add(x,-p.x),add(y,-p.y));
 33     }
 34     Point operator*(double d){
 35         return Point(x*d,y*d);
 36     }
 37     double operator*(Point p){  // 内积 点乘
 38         return add(x*p.x, y*p.y);
 39     }
 40     double operator^(Point p){//  外积 叉乘
 41         return add(x*p.y,-y*p.x);
 42     }
 43     bool operator ==(Point p){
 44         return (x==p.x )&& (y==p.y) ;
 45     }
 46     friend ostream& operator<<(ostream& os, const Point&  p)
 47     {
 48         os<<p.x<<" "<<p.y<<endl;
 49         return os;
 50     }
 51 };
 52 //判断点p0是否在线段p1p2内
 53 int on_segment(Point p1, Point p2, Point p0)
 54 {
 55     if (((p1-p0).x * (p2-p0).x <=0 )&& ((p1-p0).y * (p2-p0).y <=0))   // 中间是 &&
 56         return 1;
 57     return 0;
 58 }
 59 // 判断线段p1p2与q1是否相交
 60 int intersection(Point p1,Point p2, Point q1,Point q2)
 61 {
 62     double d1=(p2-p1)^(q1-p1);           // 计算p1p2 到q 点的转向 d1>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
",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
",x/2.0 ); // 结果 + EPS防止出现-0.00,这个程序可以不加也AC
154         }
155         else printf("0.00
");
156     }
157 }

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

  1 #include <iostream>
  2 #include <algorithm>
  3 #include <stdlib.h>
  4 #include <iostream>
  5 #include <stdio.h>
  6 #include <string>
  7 #include <string.h>
  8 #include <vector>
  9 #include <set>
 10 #include <math.h>
 11 #include <cmath>
 12 #include <map>
 13 #include <queue>
 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)<EPS*(fabs(a)+fabs(b))) return 0;
 26     return a+b;
 27 }
 28 struct Point{
 29     double x,y;
 30     Point(){}
 31     Point(double x,double y):x(x),y(y){} // 构造函数，方便代码编写
 32     Point operator +(Point p){
 33         return Point(add(x,p.x), add(y,p.y));
 34     }
 35     Point operator-(Point p){
 36         return Point(add(x,-p.x),add(y,-p.y));
 37     }
 38     Point operator*(double d){
 39         return Point(x*d,y*d);
 40     }
 41     double operator*(Point p){  // 内积 点乘
 42         return add(x*p.x, y*p.y);
 43     }
 44     double operator^(Point p){//  外积 叉乘
 45         return add(x*p.y,-y*p.x);
 46     }
 47     bool operator ==(Point p){
 48         return (sig(x-p.x) == 0 )&&( sig(y-p.y) ==0 ) ;
 49     }
 50     friend ostream& operator<<(ostream& os, const Point&  p)
 51     {
 52         os<<p.x<<" "<<p.y<<endl;
 53         return os;
 54     }
 55 };
 56 //判断点p0是否在线段p1p2内
 57 int on_segment(Point p1, Point p2, Point p0)
 58 {
 59     if (((p1-p0).x * (p2-p0).x <=0 )&& ((p1-p0).y * (p2-p0).y <=0))   // 中间是 &&
 60         return 1;
 61     return 0;
 62 }
 63 // 判断线段p1p2与q1是否相交
 64 int intersection(Point p1,Point p2, Point q1,Point q2)
 65 {
 66     double d1=(p2-p1)^(q1-p1);           // 计算p1p2 到q 点的转向 d1>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
",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
",x/2.0 ); // 结果 + EPS防止出现-0.00,这个程序可以不加也AC
158         }
159         else printf("0.00
");
160     }
161 }

计算几何 点线的综合题， 精度+ 线段相交+ 求交点 + 求面积 poj 2826 An Easy Problem?! (推荐)

计算几何点线的综合题，精度+ 线段相交+ 求交点 + 求面积 poj 2826 An Easy Problem?! (推荐)