fork download
=begin
Description:
You are a proud explorer, walking towards a range of mountains. These mountains, as they appear to you, are a series of isosceles triangles all clustered on the horizon. Check out this example image , sketched by your awesome aid nint22 (smiling-mountain not important). Your goal, given the position of the base of these triangles, how tall they are, and their base-width, is to compute the overall unique area. Note that you should not count areas that have overlapping mountains - you only care about what you can see (i.e. only count the purple areas once in the example image ).

Formal Inputs & Outputs:
Input Description:
Integer n - The number of triangles
Array of triangles T - An array of triangles, where each triangle has a position (float x), a base-length (float width), and a triangle-height (float height).

Output Description:
Print the area of the triangles you see (without measuring overlap more than once), accurate to the second decimal digit.

Notes:
#make start x, end x, slope for each side of each of the triangles
#slope = change in y / change in x
#y_intercept = y - slope(x)
 #start at left -- first line = highest line
#@lines.each {|x| puts x.inspect + ": #{eq_maker(x)}" }
#if two lines are true over any of the same range (if endx > startx of other line), check for intersection
    #y = (slope)x + height of triangle
	#make array of all intersections, sort by intercept_x, secondary sort by slope (edge case: triple intersect)
	#take the leftmost intersection
	#line whose slope is greater at that intersection point is higher
	#that line becomes new topline
=end
timer = Time.new
@top_intersects = []
@all_intersects = {}
@just_ints = []
@lines = [] #make a list of [[x1,y1],[x2,y2]], one for each line
def eq_maker(line)
	slope = (line[1][1] - line[0][1]) / (line[1][0] - line[0][0])
	y_intercept = line[0][1] - (slope * line[0][0])
	return [slope, y_intercept]
end
def intersection_finder(line1,line2) #finds the intersection point when given four points -- makes 2 lines, solves for x=y
	line1 += eq_maker(line1)
	line2 += eq_maker(line2)
	if line1[2] ==  line2[2] 
		return [line1,line2].sort_by {|x| x[1][0]}[0][1] if line1[3] == line2[3] #ultra edge case: if they're the same line, return the endpoint with the minimum x
		return [-10.0,-10.0] #less edge, but still exceptionally unlikely: if they have the same slope, return a range that doesn't exist in our board
	end
	x_int = (line2[3] - line1[3]) / (line1[2] - line2[2]) #otherwise, return the intersection point (z2 - z1) /(m1 - m2)
	y_int = (line1[2] * x_int) + line1[3]
	return [x_int, y_int]
end
def on_both?(line1,line2,int)  #.round(3) is necessary because floats suck dick
	[line1,line2].each do |x|
		return false unless int[0].round(3) >= x[0][0].round(3) && int[0].round(3) <= x[1][0].round(3)
		y_range = [x[1][1].round(3),x[0][1].round(3)].sort
		return false unless int[1].round(3) >= y_range[0] && int[1].round(3) <= y_range[1]
	end
	return true
end
def intersects(current_line) #todo: make floats not suck, and make sure it's selecting the right line (check to see if the intercept coordinates fall both on the current line and the new line length, not extended lengths 
	@all_intersects[current_line] = []
	possibilities = @lines.select {|x| @all_intersects[x].nil?} #check for intersections against all other lines that haven't already been checked for intersections (or self)
	possibilities.each do |x|
		int = intersection_finder(current_line,x)
		if on_both?(current_line,x,int)
			@just_ints.push int
			@all_intersects[int] = [current_line,x] #every intersection has exactly 2 lines -- avoids some float problems
		end
	end
	return true
end
def area_totaler(point1,point2) #totals area under any straight_line segment from x axis -- rectangle + triangle
	x_range = [point1[0],point2[0]].sort
	y_range = [point1[1],point2[1]].sort
	width = x_range[1] - x_range[0]
	rect_height = y_range[0]
	triangle_height = (y_range[1] - y_range[0])
	return (rect_height * width) + (0.5 * width * triangle_height) #rect area + triangle area
end

#format: [center-pos,base-length,height]
triangles = []
5.times do #make random triangles
	triangles.push [(rand(5000) + 2501) / 10.0 , (rand(5000) + 1) / 10.0 , (rand(5000) + 1001) / 10.0]
end

triangles.each do |x|#draw triangles
	coords = [(x[0] - (x[1] / 2)),0,	x[0],x[2],	(x[0] + (x[1] / 2)),0]
	@lines.push [[coords[0],coords[1]],[coords[2],coords[3]]]
	@lines.push [[coords[2],coords[3]],[coords[4],coords[5]]]
end

@lines.sort_by! {|x| x[0][0]} #start at left -- first line = highest line
@lines.each { |x| intersects(x) } #build all real intersections
@just_ints.sort_by! {|x| x[0]} #sort intercepts by x, move from left to right
@top_intersects.push @lines[0][0] #first point on the line is the leftmost point
last_point = @lines.sort_by {|x| x[1][0]}.last[1]
current_line = @lines[0] #start with leftmost line

@just_ints.each do |x| #iterate through intercepts, finding the top line
	if current_line[1][0] < x[0] && current_line[1][1].to_f == 0.0  #if the x of the next intercept is beyond the x of the end of our line, triangle hits the x axis, so add line endpoint and get the next line
		@top_intersects.push current_line[1]
		current_line = @lines[@lines.index {|z| z[0][0] > current_line[1][0]}]
		@top_intersects.push current_line[0]
	end
	
	if @all_intersects[x].include?(current_line) #if the next intersect includes our line, switch lines, push intersect to top_intersects
		@top_intersects.push x
		current_line = (@all_intersects[x] - [current_line])[0]
	end
	#otherwise, if the int isn't on our line, do nothing
end

@top_intersects.push last_point #add the last point after all intercepts =)

triangles.each_index do |x|
	puts "Triangle #{x+1}: center-position='#{triangles[x][0]}', width='#{triangles[x][1]}', height='#{triangles[x][2]}'"
end

area = 0
(@top_intersects.length - 1).times do |x| #count the total area under all sections
	area += area_totaler(@top_intersects[x],@top_intersects[x + 1])
end
puts "Computed area is: #{area}"

sum = 0
triangles.each do |x| #sum all the triangles, for comparison
	sum += (x[1] * x[2] * 0.5)
end
puts "Area of all triangles, including overlap, is: #{sum}"
puts "Done.  Took #{Time.new - timer} seconds."
Success #stdin #stdout 0.01s 4848KB
stdin
Standard input is empty
stdout
Triangle 1: center-position='453.7', width='312.8', height='427.3'
Triangle 2: center-position='550.6', width='312.1', height='585.7'
Triangle 3: center-position='551.5', width='373.2', height='197.0'
Triangle 4: center-position='531.7', width='408.0', height='432.9'
Triangle 5: center-position='281.1', width='388.2', height='428.4'
Computed area is: 187396.47292787468
Area of all triangles, including overlap, is: 366452.445
Done.  Took 0.001122064 seconds.