Skip to content
August 21, 2011 / oop123

Project Euler #102 – Java

You can see the problem here: Problem #102.

I cheated a little and googled for algorithms to solve this problem. Turns out there are many ways to test whether a triangle contains the origin. The algorithm I choose involves finding the triangle’s intersection with the y-axis. It’s based on the fact a triangle contains the origin iff (if and only if) it intersects the y-axis at two points – 1 above the origin and 1 below – OR when one of its vertex is the origin.

public static boolean containsOrigin(int ax, int ay, int bx, int by, int cx, int cy) {
	//one of the three vertex is origin?
	if ((ax == 0 && ay == 0) || (bx == 0 && by == 0) || (cx == 0 && cy == 0)) return false;

	List<Double> intersections = new ArrayList<Double>(2);

	//ax == 0: ay is an intersection
	//otherwise, find the intersection (note how the two conditions remove possibility of counting a vertex that's
	//on the y-axis as an intersection twice)
	if (ax == 0) intersections.add((double) ay);
	else if ((ax < 0 && bx > 0) || (ax > 0 && bx < 0)) {
		double slope = (((double) by) - ay) / (bx - ax);
		intersections.add(-slope * ax + ay);
	}

	//some copy and paste and changing single letters
	if (bx == 0) intersections.add((double) by);
	else if ((bx < 0 && cx > 0) || (bx > 0 && cx < 0)) {
		double slope = (((double) cy) - by) / (cx - bx);
		intersections.add(-slope * bx + by);
	}

	if (cx == 0) intersections.add((double) cy);
	else if ((cx < 0 && ax > 0) || (cx > 0 && ax < 0)) {
		double slope = (((double) ay) - cy) / (ax - cx);
		intersections.add(-slope * cx + cy);
	}
	
	if (intersections.size() < 2) return false;
	return ((intersections.get(0) > 0 && intersections.get(1) < 0) ||
	(intersections.get(0) < 0 && intersections.get(1) > 0));
}

Then we just need to read the text file and pass all the coordinates into the above function.

BufferedReader in = new BufferedReader(new FileReader("triangles.txt"));
int answer = 0;
for (int i = 0; i < 1000; i++) {
	String[] nums = in.readLine().split(",");
	if (containsOrigin(
		Integer.parseInt(nums[0]), Integer.parseInt(nums[1]),
		Integer.parseInt(nums[2]), Integer.parseInt(nums[3]),
		Integer.parseInt(nums[4]), Integer.parseInt(nums[5])))
			answer++;
}
System.out.println(answer);

Runs in around 40 milliseconds on my computer. CU

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: