uni/inf2440/hw4/Sequential.java

class Sequential extends Oblig4 {

	Sequential(int[] x, int[] y, int n) {
		super(x, y, n);
		name = "Sequential";
	}

	@Override
	void solve() {
		MinMaxXY minmax = findMinMax();
		MAX_X = x[minmax.maxX];
		MAX_Y = y[minmax.maxY];

		IntList indexes = new IntList(n);
		for (int i = 0; i < n; ++i)
			indexes.add(i);

		coHull = pointsRightOf(minmax.maxX, minmax.minX, indexes);
		coHull.append(pointsRightOf(minmax.minX, minmax.maxX, indexes));
	}

	class MinMaxXY {
		int minX, maxX, maxY;
	}

	MinMaxXY findMinMax() {
		int minX = 0;
		int maxX = 0;
		int maxY = 0;

		for (int i = 1; i < n; ++i) {
			if (x[i] < x[minX])
				minX = i;
			if (x[i] > x[maxX])
				maxX = i;
			if (y[i] > y[maxY])
				maxY = i;
		}

		MinMaxXY minmax = new MinMaxXY();
		minmax.minX = minX;
		minmax.maxX = maxX;
		minmax.maxY = maxY;
		return minmax;
	}

	IntList pointsRightOf(int p1, int p2, IntList indexes) {
		int p3 = -1;
		double p3dist = 0;

		int a = lineA(p1, p2);
		int b = lineB(p1, p2);
		int c = lineC(p1, p2);

		IntList nwIndexes = new IntList();

		for (int i = 0; i < indexes.size(); ++i) {
			int idx = indexes.get(i);
			if (idx == p1 || idx == p2)
				continue;

			double line = lineEquation(a, b, c, idx);
			if (line > 0)
				continue;

			nwIndexes.add(idx);

			double dist = Math.abs(dist(line, a, b));
			if (dist > p3dist) {
				p3dist = dist;
				p3 = idx;
			}
		}

		if (p3 == -1) {
			IntList l = addPointsOnLine(nwIndexes, a, b, c, p1);
			l.add(p2);

			return l;
		}

		IntList l = pointsRightOf(p1, p3, nwIndexes);
		l.append(pointsRightOf(p3, p2, nwIndexes));
		return l;
	}
}