[POJ 2826] An Easy Problem?! 【计算几何】
Problem:
Time Limit: 1000MS | Memory limit: 65536K |
Description

Your mission is to calculate how much rain these two boards can collect.
Input
Each test case consists of 8 integers not exceeding 10,000 by absolute value, x1, y1, x2, y2, x3, y3, x4, y4. (x1, y1), (x2, y2) are the endpoints of one board, and (x3, y3), (x4, y4) are the endpoints of the other one.
Output
Sample Input
2 0 1 1 0 1 0 2 1 0 1 2 1 1 0 1 2
Sample Output
1.00 0.00
Source
Solution:
本题对分类讨论的严谨度要求较高,需要分四种情况讨论:
case #1: 线段不相交,答案为 0.00;
case #2: 其中有一条线段水平放置,答案为 0.00;
case #3: 两条线段斜率正负性相同,且较高线段将开口完全覆盖,答案为 0.00;
case #4: 普通情况,答案为 | vec1 × vec2 / 2 |。
总体编程复杂度不高。
Code: O(T) [184K, 32MS]
#include<cstdio> #include<cstdlib> #include<cstring> #include<cmath> #include<iostream> #include<algorithm> #define eps 1e-10 #define dmax 1e10 #define errorpoint Point(dmax, dmax) using namespace std; int T; inline int dsgn(double dval){ if(fabs(dval) < eps) return 0; return (dval < 0) ? -1 : 1; } #define Vector Point struct Point{ double x, y; Point() {} Point(double x, double y): x(x), y(y) {} inline Vector operator - (const Point p2) const {return Vector(x - p2.x, y - p2.y);} inline bool operator == (const Point p2) const {return dsgn(x - p2.x) == 0 && dsgn(y - p2.y) == 0;} }; inline double Cross(const Vector vec1, const Vector vec2) {return vec1.x * vec2.y - vec1.y * vec2.x;} struct Segment{ Point u, v; Segment() {} Segment(Point u, Point v): u(u), v(v) {} } s1, s2; /* inline bool is_Intersected(Segment s1, Segment s2){ if(max(s1.u.x, s1.v.x) >= min(s2.u.x, s2.v.x) && min(s1.u.x, s1.v.x) <= max(s2.u.x, s2.v.x) && max(s1.u.y, s1.v.y) >= min(s2.u.y, s2.v.y) && min(s1.u.y, s1.v.y) <= max(s2.u.y, s2.v.y) && dsgn(Cross(s1.v - s1.u, s2.u - s1.u)) * dsgn(Cross(s2.v - s1.u, s1.v - s1.u)) >= 0 && dsgn(Cross(s2.v - s2.u, s1.u - s2.u)) * dsgn(Cross(s1.v - s2.u, s2.v - s2.u)) >= 0) return 1; return 0; } */ inline bool Point_on_Segment(Point p1, Segment s1){ if(dsgn(Cross(p1 - s1.u, s1.v - s1.u)) == 0 // p1 is on the line formed by s1 && p1.x >= min(s1.u.x, s1.v.x) && p1.x <= max(s1.u.x, s1.v.x) && p1.y >= min(s1.u.y, s1.v.y) && p1.y <= max(s1.u.y, s1.v.y)) return 1; // p1 is in the rectangle formed by s1 return 0; } inline Point Segment_Intersection(Segment s1, Segment s2){ double A1 = s1.u.y - s1.v.y, B1 = s1.v.x - s1.u.x, C1 = s1.u.x * s1.v.y - s1.v.x * s1.u.y; double A2 = s2.u.y - s2.v.y, B2 = s2.v.x - s2.u.x, C2 = s2.u.x * s2.v.y - s2.v.x * s2.u.y; double delta = A1 * B2 - A2 * B1; if(dsgn(delta) == 0) return errorpoint; // Two lines are parallel Point inter((B1 * C2 - B2 * C1) / delta, (A2 * C1 - A1 * C2) / delta); // Get the intersection of two lines if(Point_on_Segment(inter, s1) && Point_on_Segment(inter, s2)) return inter; return errorpoint; // The intersection is not on the two segments } inline double Slope(Segment s1){ if(dsgn(s1.v.x - s1.u.x) == 0) return dmax; return (s1.v.y - s1.u.y) / (s1.v.x - s1.u.x); } // Get the slope of s1 inline double Calc_x(Segment s1, double y){ double A1 = s1.u.y - s1.v.y, B1 = s1.v.x - s1.u.x, C1 = s1.u.x * s1.v.y - s1.v.x * s1.u.y; return -(B1 * y + C1) / A1; } // Give y to calculate x of the point (x, y) which is on s1, make sure the slope of s1 is not zero int main(){ scanf("%d", &T); while(T--){ scanf("%lf%lf%lf%lf%lf%lf%lf%lf", &s1.u.x, &s1.u.y, &s1.v.x, &s1.v.y, &s2.u.x, &s2.u.y, &s2.v.x, &s2.v.y); Point inter = Segment_Intersection(s1, s2); if(inter == errorpoint){ puts("0.00"); continue; } // Two lines have no intersection double slp1 = Slope(s1), slp2 = Slope(s2); if(dsgn(slp1) == 0 || dsgn(slp2) == 0){ puts("0.00"); continue; } // One line is horizontal if(dsgn(slp1) > 0 && dsgn(slp2) > 0){ Segment *highSeg = (slp1 > slp2) ? &s1 : &s2, *lowSeg = (slp1 > slp2) ? &s2 : &s1; if(max(highSeg->u.x, highSeg->v.x) >= max(lowSeg->u.x, lowSeg->v.x)){ puts("0.00"); continue; } } if(dsgn(slp1) < 0 && dsgn(slp2) < 0){ Segment *highSeg = (slp1 < slp2) ? &s1 : &s2, *lowSeg = (slp1 < slp2) ? &s2 : &s1; if(min(highSeg->u.x, highSeg->v.x) <= min(lowSeg->u.x, lowSeg->v.x)){ puts("0.00"); continue; } } // The opening does not point upwards Point s1top = (s1.u.y >= s1.v.y) ? s1.u : s1.v, s2top = (s2.u.y >= s2.v.y) ? s2.u : s2.v; Point contop = (s1top.y <= s2top.y) ? s1top : s2top; // Get the top water-level of the container Segment othseg = (s1top.y <= s2top.y) ? s2 : s1; Point othtop(Calc_x(othseg, contop.y), contop.y); // Get the equal-height point on the other segment double vol = fabs(Cross(contop - inter, othtop - inter) / 2); printf("%.2f\n", vol); } return 0; }
发表评论