题意：两条线段看成两块木板，雨水从上方往下垂直落下，问能接受到的水的体积
分析：恶心的分类讨论题，考虑各种情况，尤其是入口被堵住的情况，我的方法是先判断最高的两个点是否在交点的同一侧，然后看看是否高的点覆盖了低的点，用叉积判断方向，其他的情况见网上的解释。貌似没有什么卡精度的数据。最后膜拜楼教主，难以望其项背。。。
/************************************************
* Author :Running_Time
* Created Time :2015/10/30 星期五 18:36:27
* File Name :POJ_2826.cpp
************************************************/ #include <cstdio>
#include <algorithm>
#include <iostream>
#include <sstream>
#include <cstring>
#include <cmath>
#include <string>
#include <vector>
#include <queue>
#include <deque>
#include <stack>
#include <list>
#include <map>
#include <set>
#include <bitset>
#include <cstdlib>
#include <ctime>
using namespace std; #define lson l, mid, rt << 1
#define rson mid + 1, r, rt << 1 | 1
typedef long long ll;
const int N = 1e5 + 10;
const int INF = 0x3f3f3f3f;
const int MOD = 1e9 + 7;
const double EPS = 1e-10;
const double PI = acos (-1.0);
int dcmp(double x) {
if (fabs (x) < EPS) return 0;
else return x < 0 ? -1 : 1;
}
struct Point {
double x, y;
Point () {}
Point (double x, double y) : x (x), y (y) {}
Point operator + (const Point &r) const {
return Point (x + r.x, y + r.y);
}
Point operator - (const Point &r) const {
return Point (x - r.x, y - r.y);
}
Point operator * (double p) const {
return Point (x * p, y * p);
}
Point operator / (double p) const {
return Point (x / p, y / p);
}
bool operator < (const Point &r) const {
return x < r.x || (!dcmp (x - r.x) && y < r.y);
}
bool operator == (const Point &r) const {
return dcmp (x - r.x) == 0 && dcmp (y - r.y) == 0;
}
};
typedef Point Vector;
Point read_point(void) {
double x, y;
scanf ("%lf%lf", &x, &y);
return Point (x, y);
}
double dot(Vector A, Vector B) {
return A.x * B.x + A.y * B.y;
}
double cross(Vector A, Vector B) {
return A.x * B.y - A.y * B.x;
}
Point line_line_inter(Point p, Vector V, Point q, Vector W) {
Vector U = p - q;
double t = cross (W, U) / cross (V, W);
return p + V * t;
}
bool can_inter(Point a1, Point a2, Point b1, Point b2) {
double c1 = cross (a2 - a1, b1 - a1), c2 = cross (a2 - a1, b2 - a1),
c3 = cross (b2 - b1, a1 - b1), c4 = cross (b2 - b1, a2 - b1);
return dcmp (c1) * dcmp (c2) <= 0 && dcmp (c3 * c4) <= 0;
}
double area_triangle(Point a, Point b, Point c) {
return fabs (cross (b - a, c - a)) / 2.0;
} int main(void) {
int T; scanf ("%d", &T);
Point a1, a2, b1, b2;
while (T--) {
a1 = read_point ();
a2 = read_point ();
b1 = read_point ();
b2 = read_point (); //a1，b1是纵坐标较高的点
if (dcmp (a1.y - a2.y) < 0 || (dcmp (a1.y - a2.y) == 0 && dcmp (a1.x - a2.x) > 0)) swap (a1, a2);
if (dcmp (b1.y - b2.y) < 0 || (dcmp (b1.y - b2.y) == 0 && dcmp (b1.x - b2.x) > 0)) swap (b1, b2);
if (dcmp (a1.x - a2.x) == 0 && dcmp (b1.x - b2.x) == 0) { //竖直平行
puts ("0.00"); continue;
}
if (dcmp (a1.y - a2.y) == 0 || dcmp (b1.y - b2.y) == 0) { //水平平行
puts ("0.00"); continue;
}
if (dcmp (cross (a1 - a2, b1 - b2)) == 0) { //共线
puts ("0.00"); continue;
}
if (!can_inter (a1, a2, b1, b2)) { //不能相交
puts ("0.00"); continue;
}
Point p = line_line_inter (a1, a2 - a1, b1, b2 - b1), q;
if (dcmp (a1.y - p.y) <= 0 || dcmp (b1.y - p.y) <= 0) { //有一个点纵坐标低于交点
puts ("0.00"); continue;
}
double ans = 0.0;
if (dcmp (a1.y - b1.y) == 0) {
ans = area_triangle (a1, b1, p);
}
else if (dcmp (a1.y - b1.y) < 0) {
if (dcmp (a1.x - p.x) > 0 && dcmp (b1.x - p.x) > 0) {
if (dcmp (b1.x - a1.x) >= 0 && cross (a1 - p, b1 - p) >= 0) { //入口被覆盖，以下同
puts ("0.00"); continue;
}
}
else if (dcmp (a1.x - p.x) < 0 && dcmp (b1.x - p.x) < 0) {
if (dcmp (b1.x - a1.x) <= 0 && cross (b1 - p, a1 - p) >= 0) {
puts ("0.00"); continue;
}
}
q = line_line_inter (a1, Vector (1, 0), b1, b2 - b1);
ans = area_triangle (a1, q, p);
}
else {
if (dcmp (a1.x - p.x) > 0 && dcmp (b1.x - p.x) > 0) {
if (dcmp (a1.x - b1.x) >= 0 && cross (b1 - p, a1 - p) >= 0) {
puts ("0.00"); continue;
}
}
else if (dcmp (a1.x - p.x) < 0 && dcmp (b1.x - p.x) < 0) {
if (dcmp (a1.x - b1.x) <= 0 && cross (a1 - p, b1 - p) >= 0) {
puts ("0.00"); continue;
}
}
q = line_line_inter (a1, a2 - a1, b1, Vector (1, 0));
ans = area_triangle (b1, q, p);
}
double eps = 1e-8;
printf ("%.2f\n", ans + eps);
} //cout << "Time elapsed: " << 1.0 * clock() / CLOCKS_PER_SEC << " s.\n"; return 0;
}