POJ_2826
这个题目暂且不讨论精度的问题了，因为discuss上面有相当一部分人在吐槽精度，所以如果你A不掉的话可以考虑discuss上面的一些建议。
这个题目确实要考虑到比较多的情况，我们不妨一一分析。
首先，如果两个线段都没交点了，肯定存不了水，因此我们不妨先剔除掉不相交的情况。为了能简化后面叉积的讨论，我们可以先将平行的情况特判一下。
接下来，我们就讨论：如果两个线段有交点就一定能存水吗？
比较容易画出一种情况，就是开口向下，同时上方没有开口的情况，也就是把sample1的形状上下颠倒一下。但对于一般的问题呢？
我们不妨将水填上，会发现这个类似木桶效应，水存多少是取决于最低的y的，这样如果我们找到决定水平面的那个y，就可以利用定比分点公式找到这个水平面与两个线段的交点，如果再能将两个线段的交点求出的话，无论是直接用底乘高除2还是用叉积算有向面积再除2，都能得到存水的面积。
到这里，这个问题还没有完全解决，因为这个题目是有背景的咯，这两个板子是接雨水的，如果一头的板子比较长的话就会把可以进水的口给遮住了，这样即便能存水，但水进不去的话最终积水量还是0。
对于判断入水口是否会被遮住，我们算出的水平面会和两个线段各有一个交点，根据这两个交点的x的关系就可以判断出两条线段左右的位置关系了，这样只要右边线段的上端点在左边线段的上端点的左方或正上方，就会把入水口给遮住了。
#include<stdio.h>
#include<string.h>
#define zero 1e-8
double x1, y1, x2, y2, x3, y3, x4, y4;
double fabs(double x)
{
return x < 0 ? -x : x;
}
double min(double x, double y)
{
return x < y ? x : y;
}
double max(double x, double y)
{
return x > y ? x : y;
}
int dcmp(double x)
{
if(fabs(x) < zero)
return 0;
if(x < 0)
return -1;
return 1;
}
double det(double x1, double y1, double x2, double y2)
{
return x1 * y2 - x2 * y1;
}
void solve()
{
int i, j, k;
double t1, t2, t3, t4, x, y, ans, tx1, ty1, tx2, ty2, ty, t;
t1 = det(x2 - x1, y2 - y1, x3 - x1, y3 - y1);
t2 = det(x2 - x1, y2 - y1, x4 - x1, y4 - y1);
t3 = det(x4 - x3, y4 - y3, x1 - x3, y1 - y3);
t4 = det(x4 - x3, y4 - y3, x2 - x3, y2 - y3);
if(dcmp(t1) * dcmp(t2) <= 0 && dcmp(t3) * dcmp(t4) <= 0)
{
x = (fabs(t2) * x3 + fabs(t1) * x4) / (fabs(t1) + fabs(t2));
y = (fabs(t2) * y3 + fabs(t1) * y4) / (fabs(t1) + fabs(t2));
ty = min(max(y1, y2), max(y3, y4));
if(y1 > y2)
{
t = y1, y1 = y2, y2 = t;
t = x1, x1 = x2, x2 = t;
}
if(y3 > y4)
{
t = y3, y3 = y4, y4 = t;
t = x3, x3 = x4, x4 = t;
}
tx1 = (fabs(ty - y1) * x2 + fabs(ty - y2) * x1) / (fabs(ty - y1) + fabs(ty - y2));
ty1 = (fabs(ty - y1) * y2 + fabs(ty - y2) * y1) / (fabs(ty - y1) + fabs(ty - y2));
tx2 = (fabs(ty - y3) * x4 + fabs(ty - y4) * x3) / (fabs(ty - y3) + fabs(ty - y4));
ty2 = (fabs(ty - y3) * y4 + fabs(ty - y4) * y3) / (fabs(ty - y3) + fabs(ty - y4));
ans = fabs(det(tx2 - x, ty2 - y, tx1 - x, ty1 - y)) / 2;
if(tx1 < tx2)
{
if(dcmp(x4 - x2) <= 0)
{
printf("0.00\n");
return ;
}
}
else
{
if(dcmp(x4 - x2) >= 0)
{
printf("0.00\n");
return ;
}
}
printf("%.2lf\n", ans);
}
else
printf("0.00\n");
}
int main()
{
int t;
scanf("%d", &t);
while(t --)
{
scanf("%lf%lf%lf%lf%lf%lf%lf%lf", &x1, &y1, &x2, &y2, &x3, &y3, &x4, &y4);
if(dcmp((y2 - y1) * (x4 - x3) - (y4 - y3) * (x2 - x1)) == 0)
printf("0.00\n");
else
{
if(dcmp(y2 - y1) == 0 || dcmp(y4 - y3) == 0)
printf("0.00\n");
else
solve();
}
}
return 0;
}