Java 试题 历届试题 平面切分【第十一届】【省赛】【B组】

（纪念从这一题学的的很多东西）

题意：n条直线共划分为多少个平面
没有直线平面为1
一条直线平面为2
两条直线相交平面为4，不相交平面为3，即平面数=交点数+1
三条直线的情况以此类推

∵ n>=1
∴ 平面数>=2

易知：
总平面数=2+Σ（第i条直线与第j条直线相交点的个数+1）
本题的给的样例是三条线重合到1个点，所以点不能重复计算，考虑使用set。
但是java使用set不能直接添加数组，需要自定义一个类，重写equals和hashCode方法（这个简单，自动生成就行）。
然后用set过滤掉重复的线，再转存到放线段的数组中，便于点的计算
用完set之后清空，我们就继续使用set存点啦（节省空间）
然后二元一次方程求解交点存set里头
但是计算的时候会出现-0.0和0.0的情况，set会直接认为这俩是不一样的，所以点的个数也会增加。这时候加上0.0即可解决该问题，具体原因在这，就不具体说了。

代码如下：

import java.io.*;
import java.util.*;

public class Main {

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StreamTokenizer re = new StreamTokenizer(br);
		PrintWriter pr = new PrintWriter(new OutputStreamWriter(System.out));
		int n;
		double pa[] = new double[1010], pb[] = new double[1010];//点a，点b
		Set set = new HashSet();
		re.nextToken();
		n = (int) re.nval;

		for (int i = 1; i <= n; i++) {
			re.nextToken();
			int x = (int) re.nval;
			re.nextToken();
			int y = (int) re.nval;
			set.add(new Double(new double[] { x, y }));
		}
		Iterator it = set.iterator();
		int len = 0;
		while (it.hasNext()) {
			Double d = it.next();
			double[] dary = d.getAry();
			len++;
			pa[len] = dary[0];
			pb[len] = dary[1];// len是从1开始的，不是从0开始的

		}

		set.clear();
		int ans = 2;
		for (int i = 2; i <= len; i++) {// 此处要特别注意范围！！
			for (int j = i - 1; j >= 1; j--) {// 点的数组范围是[1,len]而不是[0,len-1]
				if (pa[i] == pa[j])
					continue;// 两直线平行没有交点，跳过
				double x = (pb[i] - pb[j]) / (pa[j] - pa[i]) + 0.0;// 注意0.0和-0.0的情况
				double y = pa[i]*x+pb[i] + 0.0;
				set.add(new Double(new double[] { x, y }));
			}
			int tmp = set.size();
			ans += (tmp + 1);
			set.clear();
		}
		pr.print(ans);
		pr.flush();

	}

	static class Double {
		private double ary[];

		public Double(double[] ary) {
			super();
			this.ary = ary;
		}

		public double[] getAry() {
			return ary;
		}

		@Override
		public int hashCode() {
			final int prime = 31;
			int result = 1;
			result = prime * result + Arrays.hashCode(ary);
			return result;
		}

		@Override
		public boolean equals(Object obj) {
			if (this == obj)
				return true;
			if (obj == null)
				return false;
			if (getClass() != obj.getClass())
				return false;
			Double other = (Double) obj;
			if (!Arrays.equals(ary, other.ary))
				return false;
			return true;
		}
	}
}