contourline.java

上海交通大学研究生算法分析课的作业.实现了<<算法引论-一种创造性方法>>(Udi Manber 黄林鹏 电子工业出版社)第五章中的大部分算法

//建筑物轮廓

//接算法是基于增加一栋建筑到轮廓中。归纳假设是简单的。假定已知如何求解n-1栋建筑的问题，然后我们增加第n栋建筑。对于只有一栋建筑，问题是平凡的。
//为了增加建筑Bn到轮廓中，我们需要把它和已有的轮廓贯穿相交(见图5.6)。
//令Bn是(5，9，26)。我们先从左到右扫描轮廓，以找到Bn左侧安置的点(即寻找适当的x坐标，在本例中是5)。
//在此情形下，“盖住”5的水平线是从3到9，并且它的高度是13。
//现在扫描轮廓，考虑下一条水平线，并且当Bn的高度高于已有的高度时进行调整。
//当到达大于Bn右侧的x坐标时，就停止。

//测试数据：(1,2,2),(3,4,2),(0,5,1)

import java.io.*;
import java.util.*;
class ContourLine 
	{
		static InputStreamReader in;
		static BufferedReader reader;

		static
		{
			in=new InputStreamReader(System.in);
			reader=new BufferedReader(in);
		}

		static String readString()
		{
			String s="";
			try
			{ 
				s=reader.readLine();
			}
			catch(IOException e)
			{
				System.out.println(e);
				System.exit(0);
			} 
			return s;
		}

		static double String2Double(String s)
		{
			double d=0.0;
			try
			{
				d=Double.parseDouble(s);
			}
			catch(Exception e)
			{
				System.out.println("输入的数据类型不对，程序将退出");
				System.exit(0);
			}  
			return d;
		}

		static ArrayList<Double> Contour(double[][] d)
		{
			ArrayList<Double> r = new ArrayList<Double> ();
			
			r.add(Double.NEGATIVE_INFINITY);
			r.add(0.0);
			r.add(Double.POSITIVE_INFINITY);
			r.add(0.0);

			for (int i =0; i<d.length; i++)
			{
				double x1 =d[i][0];
				double x2 =d[i][1];
				double y =d[i][2];
				int j = 0;
				while (x2 > r.get(j))
				{
					if (x1 < r.get(j))
					{
						if (x1 > r.get(j-2))
						{
							if (y > r.get(j-1))
							{
								r.add(j, y);
								r.add(j, x1);
								j = j + 2;
								continue;
							}
						}
						else
						if (y >= r.get(j+1))
						{
							if (y < r.get(j - 1))
							{
								r.set(j + 1, y);
								j = j + 2;
								continue;
							}
							else
							{
								r.remove(j);
								r.remove(j);
								continue;
							}
						}
					}
					else
					if (x1 == r.get(j))
					{
						if (y > r.get(j+1))
						{
							r.set(j+1, y);
							j = j + 2;
							continue;
						}
					}
					else
					if (x2 < r.get(j+2))
					{
						r.add(j+2, y);
						r.add(j+2, x1);
						j = j + 4;
						break;
					}
					j = j + 2;
				}

				if (x2 < r.get(j))
				{
					if (y > r.get(j+1))
					{
						r.add(j,x2);
						r.add(j+1,r.get(j+2));
					}
				}
			}
			r.remove(0);
			r.remove(0);
			r.remove(r.size()-1);
			r.remove(r.size()-1);
			return r;
		}

		static void PrintCL(ArrayList<Double> da)
		{
			System.out.print("轮廓线为：(   ");
			for (double d : da )
			{
				System.out.print(d + "   ");
			}
			System.out.println(")");
		}

		public static void main(String _args[]) 
		{
			System.out.println("建筑物轮廓");
			System.out.print("请输入建筑外型（格式如：(1,3,2),(2,4,5)）：");
			String strInput = readString();
			strInput = strInput.substring(1, strInput.length()-1);
			String[] strGroup = strInput.split("\\),\\(");
			if (strGroup.length == 0)
			{
				System.exit(0);
			}

			double[][] dblEm = new double[strGroup.length][3];
			for (int i = 0; i < strGroup.length; i++)
			{
				String[] strEm = strGroup[i].split(",");
				if (strEm.length != 3)
				{
					System.out.println("输入的数据格式不对，程序将退出");
					System.exit(0);
				}
				dblEm[i][0] =String2Double(strEm[0]);
				dblEm[i][1] =String2Double(strEm[1]);
				dblEm[i][2] =String2Double(strEm[2]);
				if (dblEm[i][0] >= dblEm[i][1])
				{
					System.out.println("输入的数据的值不对，程序将退出");
					System.exit(0);
				}
			}

			PrintCL(Contour(dblEm));
        }
    }