WUSTOJ 1264: 祈雨

Description

在持续了X天的干旱之后，ACM俱乐部决定由LCM去请求雨大师XH祈雨，CMS则准备工具收集雨水，由于ACM俱乐部中有一个逆天的存在，BobLee 他能够用意念用两条线段接水。具体操作如下

现在CMS想要知道BobLee最终能接到多少雨水。（雨水垂直下落，不存在任何偏斜，雨水的多少用面积进行计算）

Input

存在多组输入数据

        每组数据两行（都是整数）

        第一行 x1 y1 x2 y2 代表第一条线段的两个端点的坐标

        第二行 x3 y3 x4 y4 代表第二条线段的两个端点的坐标

Output

输出BobLee能够接的雨水量（输出保留两位小数）

Sample Input

Sample Output

1.00

0.00

题目分析

题目大意就是用两根线段摆出一个形状，计算最终能接到多少水。下面来看一下接不到水的情况有哪些：

当两条线段中至少有一条线段是水平的，那么肯定是接不到水的，结果为0.00；
当两条线段是平行的，也是接不到水的，结果为0.00；
当两条线段没有交点时，也是接不到水的，结果为0.00。

当以上三种情况都排除后，说明两条线段有交点。以上只是最简单的排除。但实际上，还有两种情况也是接不到水的。如下图所示：

以上两幅图中，虽然这两条线段不水平而且相交，但是线段A将线段B完全挡住了，雨水都顺着线段A和线段B的右（左）上侧滑走了，根本无法积攒到他们中间的“漏斗”中。因此这种情况结果依然是0.00。

到这里了，只要自己细心一点，代码完全是可以写出来的。如果说上述情况都考虑到了。下面说一些细节问题：

int型相除结果是不保留小数的，应该都知道。建议此题所有数据均用浮点型，虽然题目说的输入数据是整型的，但是用浮点型更稳妥；
有没有分母为零的情况，仔细检查一下；
计算面积过程中，计算某些点的坐标，公式有没有写错；
上面的最关键的那种接不到水的情况，判断错没错；
注意一些相等的地方有没有漏掉。

下面两组我自己的测试数据，算对的数据我就不提供了，毕竟每个人代码都不一样。（代码不同，以下数据仅供参考）

1 1 0 0

0 0 3 2

正确结果：0.25

测试小数，因为我之前用的是int型保存输入数据的，恰好代码中有的地方漏乘了1.0，结果就算成了0.00

1   1   0   0

-2  2   0   0

正确结果：1.00

我之前的代码算成了3.00，原因是一个if-else分支里面的代码错了

如果说你还是找不出来错误，那就只能用最不推荐的办法了——阅读下面这个长达200行的代码了。如有不清楚的地方，请讨论或留言告知本人，我会根据情况稍作修改。

代码

代码有点长，后期会整理代码，按方法讲解。主要是细节问题。

无语了，我觉得下面代码不怎么好，然后准备重构一下。然鹅，完全重写了两遍，有的地方甚至还优化了，，，奈何（一直被模仿，从未被超越）居然硬生生出现在了我身上，，，后来写的我觉得很对的代码，提交一次没过，心凉了。你们就将就阅读下面这个“烂”（奇葩的是它AC了）代码吧。。。

PS:我自己都不想再看，乐意的话，不懂的地方就直接问我吧。。

另外，我还发现了这个代码有点问题，输入下面这组数据的时候

0 0 0 1

0 0 1 1

正确结果：0.50

但是我自己运行结果：0.00

然而提交代码是正确的。。。所以，OJ测试数据应该没有那种一条线段垂直，一条线段斜着的这种情况。

我已经不想改代码了，毕竟：一直被模仿，从未被超越QAQ

/**

 * 用时：274ms

 * @author wowpH

 * @version A1.0

 * @date 2019年4月13日 下午3:32:04

 */

import java.util.Scanner;

public class Main {

	private Scanner sc;

	// 输入数据，线段端点坐标

	private double x1, y1, x2, y2, x3, y3, x4, y4;

	private double area; // 面积，也就是接到的雨水

	private double intersectionX, intersectionY; // 交点

	public Main() {

		sc = new Scanner(System.in);

		while (sc.hasNext()) {

			area = 0; // 初始化接到的雨水为0

			input(); // 输入数据

			// 两条线都不能水平

			if (y1 != y2 && y3 != y4) {

				// 两条线段不平行

				if (false == parallel()) {

					// 两条线段相交

					if (intersect()) {

						calculate(); // 计算面积

					}

				}

			}

			System.out.printf("%.2f\n", area); // 输出接到的雨水

		}

		sc.close();

	}

	private void input() {

		x1 = sc.nextDouble();

		y1 = sc.nextDouble();

		x2 = sc.nextDouble();

		y2 = sc.nextDouble();

		x3 = sc.nextDouble();

		y3 = sc.nextDouble();

		x4 = sc.nextDouble();

		y4 = sc.nextDouble();

	}

	/**

	 * @return 两条线段是否平行，是返回true，否返回false

	 */

	private boolean parallel() {

		// 第一条线段垂直

		if (x1 == x2) {

			// 第二条线段也垂直

			if (x3 == x4) {

				return true; // 两条都垂直，平行

			}

		} else { // 第一条不垂直

			// 第二条不垂直

			if (x3 != x4) {

				// 两条都不垂直，计算斜率

				double k1, k2;

				k1 = (y1 - y2) * 1.0 / (x1 - x2);

				k2 = (y3 - y4) * 1.0 / (x3 - x4);

				if (k1 == k2) {

					return true; // 斜率相同，平行

				}

			}

		}

		return false; // 否则不平行

	}

	/**

	 * @return 两条线段是否相交，是返回true，否返回false

	 */

	private boolean intersect() {

		double xa = x1 - x2;

		double xb = x3 - x4;

		double ya = y1 - y2;

		double yb = y3 - y4;

		double xya = x1 * y2;

		double xyb = x2 * y1;

		double xyc = x3 * y4;

		double xyd = x4 * y3;

		double molecule = (xa * (xyc - xyd) - xb * (xya - xyb));

		double denominator = (xb * ya - xa * yb);

		intersectionX = molecule / denominator; // 相交点x坐标

		if (intersectionX < x1 && intersectionX < x2) {

			return false; // 相交点X坐标超出第一条线段

		} else if (intersectionX > x1 && intersectionX > x2) {

			return false; // 相交点X坐标超出第一条线段

		} else {

			if (intersectionX < x3 && intersectionX < x4) {

				return false; // 相交点X坐标超出第二条线段

			} else if (intersectionX > x3 && intersectionX > x4) {

				return false; // 相交点X坐标超出第二条线段

			} else {

				intersectionY = ya / xa * intersectionX + (xya - xyb) / xa;

				return true;

			}

		}

	}

	private void calculate() {

		// 分别表示比交点高的线段端点坐标

		double pointAX, pointAY, pointBX, pointBY;

		if(y1 > intersectionY) {

			pointAX = x1;

			pointAY = y1;

		} else if(y2 > intersectionY) {

			pointAX = x2;

			pointAY = y2;

		} else {

			return;

		}

		if(y3 > intersectionY) {

			pointBX = x3;

			pointBY = y3;

		} else if(y4 > intersectionY) {

			pointBX = x4;

			pointBY = y4;

		} else {

			return;

		}

		double temp;

		if(pointAX == pointBX) {

			return;

		} else if(pointAX > pointBX) {

			temp = pointAX;

			pointAX = pointBX;

			pointBX = temp;

			temp = pointAY;

			pointAY = pointBY;

			pointBY = temp;	// 注意别写错

		}

		double ka, kb;

		ka = (pointAY - intersectionY) / (pointAX - intersectionX);

		kb = (pointBY - intersectionY) / (pointBX - intersectionX);

		if(ka < kb && kb < 0 || ka > 0 && ka < kb) {

			return;

		}

		// 一定能接到雨水

		double surfaceIntersectionX, surfaceIntersectionY;	// 水面交点

		double xa, ya, xya, xyb;

		if(pointAY > pointBY) {

			surfaceIntersectionY = pointBY;

			xa = pointAX - intersectionX;

			ya = pointAY - intersectionY;

			xya = pointAX * intersectionY;

			xyb = pointAY * intersectionX;

			surfaceIntersectionX = surfaceIntersectionY * xa / ya - (xya - xyb) / ya;

			area = (pointBX - surfaceIntersectionX) * (surfaceIntersectionY - intersectionY) / 2;

		} else {

			surfaceIntersectionY = pointAY;

			xa = pointBX - intersectionX;

			ya = pointBY - intersectionY;

			xya = pointBX * intersectionY;

			xyb = pointBY * intersectionX;

			surfaceIntersectionX = surfaceIntersectionY * xa / ya - (xya - xyb) / ya;

			area = (surfaceIntersectionX - pointAX) * (surfaceIntersectionY - intersectionY) / 2;

		}

	}

	/**

	 * @param args

	 */

	public static void main(String[] args) {

		new Main();

	}

}

写在最后：

如需转载，请于标题下注明链接形式的wowpH的博客即可；
代码原创，如需公开引用，不能删除首行注释（作者，版本号，时间等信息）。

巴特西

1264: 祈雨（Java）