vjudge链接：https://vjudge.net/problem/POJ-2826
题意很简单，天上下雨，用两根线段接水，问能接住多少面积的水。
看起来很简单，然后WA了5发。。。 首先判断两根线段是否相交，若不相交则显然不能接到水。 然后求交点p。分别求出两条线段的端点中较上面的端点p1, p2。然后以交点为新的原点，p1 -= p, p2 -= p。这样就映射到了以p为原点的坐标系中。问题转化为p1、原点、p2形成的碗能不能接到水。
注意雨是从天下下的，因此需要特判一下较高的线段会不会把较低的线段挡住。 y = min(p1.y, p2.y)，显然y>=0 如果y=0，那么显然不能接到水。 y>0时，安排p1和p2的顺序，使得p1.y <= p2.y。然后看一下p1.x和p2.x是否在同一侧，如果不在则一定不会挡住。如果都在左侧，则看一下p1O是不是在p2O左侧以及fabs(p1.x)是否小于等于fabs(p2.x)，若是，则说明p1被p2挡住了。右侧同理。 没有被挡住的情况就正常求了。不赘述。
赠送一波数据： 100 0 1 1 0 1 0 2 1
0 1 2 1 1 0 1 2
0 0 1 1 2 0 0 2
0 1 1 0 2 0 3 1
2 0 0 2 1 1 2 2
-10000 10000 0 -10000 0 -10000 10000 10000
0 0 3 3 0 2 2 0
0 3 3 0 1 0 3 2
0 3 3 0 1 1 3 0
0 0 2 1 0 0 3 3
0 0 3 3 0 0 3 3
0 2 2 0 0 1 2 0
0 0 2 1 0 0 2 2
0 0 3 3 0 0 1 2
>> 1.00 0.00 0.00 0.00 1.00 200000000.00 1.00 1.00 0.00 0.00 0.00 0.00 0.00 1.00
代码：
#include <cstdio> #include <cmath> #include <algorithm> using namespace std; #define MAXN 100011 template <typename T> T sq(T x) { return x * x; } const double eps = 1e-8, pi = acos(-1.0); int sgn(double x) { return x < -eps ? -1 : (x > eps ? 1 : 0); } struct VEC { double x, y; bool operator == (const VEC& b) const { return sgn(x - b.x) == 0 && sgn(y - b.y) == 0; } bool operator < (const VEC& b) const { return sgn(y - b.y) == 0 ? sgn(x - b.x) < 0 : y < b.y; } VEC operator - (const VEC& b) const { return VEC{x - b.x, y - b.y}; } VEC operator + (const VEC& b) const { return VEC{x + b.x, y + b.y}; } double len() const { return hypot(x, y); } double dist(const VEC& b) const { return (*this - b).len(); } double len2() const { return sq(x) + sq(y); } double dist2(const VEC& b) const { return (*this - b).len2(); } VEC operator * (double k) const { return VEC{x * k, y * k}; } VEC trunc(double l) const { double ori = len(); if (!sgn(ori)) return *this; return *this * (l / ori); } VEC operator / (double k) const { return VEC{x / k, y / k}; } VEC norm() const { return *this / len(); } double operator ^ (const VEC& b) const { return x * b.y - y * b.x; } double operator * (const VEC& b) const { return x * b.x + y * b.y; } // The angle between *this and b //anticlockwise is plus double rad_di(const VEC& b) const { return atan2(*this ^ b, *this * b); } double rad(const VEC& b) const { return fabs(rad_di(b)); //return asin(fabs(*this ^ b) / (len() * b.len())); } VEC rotleft() const { return VEC{-y, x}; } VEC rotright() const { return VEC{y, -x}; } VEC rot(double a) const { double c = cos(a), s = sin(a); return VEC{x * c - y * s, x * s + y * c}; } //Independent //0 <= slope < pi double slope() const { double ans = atan2(y, x); if (sgn(ans) < 0) ans += pi; else if (sgn(ans - pi) == 0) ans -= pi; return ans; } double cross(const VEC& p1, const VEC& p2) const { return (p1 - *this) ^ (p2 - *this); } //-1: left //0: parallel //1: right int relation(const VEC& b) const { return sgn(b ^ *this); } VEC operator - () const { return VEC{-x, -y}; } bool SameDi(const VEC& b) const { return sgn(x) == sgn(b.x) && sgn(y) == sgn(b.y); } void input() { scanf("%lf%lf", &x, &y); } }; struct LINE { VEC s, v; LINE() {} LINE(const VEC& _s, const VEC& _v) : s(_s), v(_v) {} void set(const VEC& _s, double a) { s = _s; v = {cos(a), sin(a)}; } //ax + by + c = 0 void set(double a, double b, double c) { v = {b, -a}; s = fabs(a) > fabs(b) ? VEC{-c / a, 0} : VEC{0, -c / b}; } //-1: left //0: on it //1: right int relation(const VEC& p) const { return sgn((p - s) ^ v); } //0: parallel //1: coincide //2: intersect int relation(const LINE& b) const { if (v.relation(b.v) == 0) return b.relation(s) == 0; return 2; } //Assume that they intersect VEC CrossPoint(const LINE& b) const { double t = ((b.s - s) ^ b.v) / (v ^ b.v); return s + v * t; } //left is plus double dist_di(const VEC& p) const { return (v ^ (p - s)) / v.len(); } double dist(const VEC& p) const { return fabs(dist_di(p)); } VEC projection(const VEC& p) const { VEC v1 = v.norm(); return v1 * ((p - s) * v1) + s; } VEC symmetry(const VEC& p) const { VEC p0 = projection(p); return p0 * 2 - p; } void SetAngularBisector(const VEC& a, const VEC& b, const VEC& c) { set(a, (atan2(b.y - a.y, b.x - a.x) + atan2(c.y - a.y, c.x - a.x)) / 2); } }; struct SEG : LINE { VEC e; SEG() {} SEG(const VEC& _s, const VEC& _e) : e(_e), LINE(_s, _e - _s) {} bool exclusive_between(const VEC& p) const { return sgn((p - s) * (p - e)) < 0; } bool between(const VEC& p) const { return sgn((p - s) * (p - e)) <= 0; } bool OnSeg(const VEC& p) const { return sgn((p - s) ^ v) == 0 && between(p); } //0: Not cross //1: Just cross (unnorm cross 非规范相交) //2: Cross inner (norm cross 规范相交) int relation(const SEG& b) const { int d1 = sgn(v ^ (b.s - s)); int d2 = sgn(v ^ (b.e - s)); int d3 = sgn(b.v ^ (s - b.s)); int d4 = sgn(b.v ^ (e - b.s)); if ((d1 ^ d2) == -2 && (d3 ^ d4) == -2) return 2; else return (d1 == 0 && between(b.s)) || (d2 == 0 && between(b.e)) || (d3 == 0 && b.between(s)) || (d4 == 0 && b.between(e)); } int relation(const LINE& b) const { int d1 = sgn(b.v ^ (s - b.s)); int d2 = sgn(b.v ^ (e - b.s)); if ((d1 ^ d2) == -2) return 2; else return d1 == 0 || d2 == 0; } double dist(const VEC& p) const { if (sgn((p - s) * v) < 0 || sgn((p - e) * v) > 0) return min(p.dist(s), p.dist(e)); return LINE::dist(p); } double dist(const SEG& b) const { return relation(b) ? 0 : min(min(dist(b.s), dist(b.e)), min(b.dist(s), b.dist(e))); } }; double GetX(const VEC& v, double y) { return v.x / v.y * y; } int main() { int T; scanf("%d", &T); while (T--) { SEG a, b; a.s.input(); a.e.input(); a.v = a.e - a.s; b.s.input(); b.e.input(); b.v = b.e - b.s; bool fail = false; if (!a.relation(b)) { fail = true; } else { VEC p = a.CrossPoint(b); VEC p1 = a.s.y > a.e.y ? a.s : a.e; VEC p2 = b.s.y > b.e.y ? b.s : b.e; p1 = p1 - p; p2 = p2 - p; double y = min(p1.y, p2.y); if (sgn(y)) { if (p1.y > p2.y) { swap(p1, p2); } int side = sgn(p1.x); if (0 == (side ^ sgn(p2.x)) && p2.relation(p1) == side && sgn(fabs(p1.x) - fabs(p2.x)) <= 0) { fail = true; } if (!fail) { double x1 = GetX(p1, y), x2 = GetX(p2, y); if (x1 > x2) swap(x1, x2); printf("%.2f\n", (x2 - x1) * y / 2 + eps); } } else { fail = true; } } if (fail) { puts("0.00"); } } return 0; }