题目来源: 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 #include2 #include 3 #include 4 #include 5 #include 6 #include 7 #include 8 #include 9 #include 10 #include 11 #include 12 #include
有 sig(x)函数的代码如下:
1 #include2 #include 3 #include 4 #include 5 #include 6 #include 7 #include 8 #include 9 #include 10 #include 11 #include 12 #include