fork download
copy 
  1. =begin
  2. Description:
  3. 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 ).
  4.  
  5. Formal Inputs & Outputs:
  6. Input Description:
  7. Integer n - The number of triangles
  8. 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).
  9.  
  10. Output Description:
  11. Print the area of the triangles you see (without measuring overlap more than once), accurate to the second decimal digit.
  12.  
  13. Notes:
  14. #make start x, end x, slope for each side of each of the triangles
  15. #slope = change in y / change in x
  16. #y_intercept = y - slope(x)
  17.  #start at left -- first line = highest line
  18. #@lines.each {|x| puts x.inspect + ": #{eq_maker(x)}" }
  19. #if two lines are true over any of the same range (if endx > startx of other line), check for intersection
  20.     #y = (slope)x + height of triangle
  21. 	#make array of all intersections, sort by intercept_x, secondary sort by slope (edge case: triple intersect)
  22. 	#take the leftmost intersection
  23. 	#line whose slope is greater at that intersection point is higher
  24. 	#that line becomes new topline
  25. =end
  26. timer = Time.new
  27. @top_intersects = []
  28. @all_intersects = {}
  29. @just_ints = []
  30. @lines = [] #make a list of [[x1,y1],[x2,y2]], one for each line
  31. def eq_maker(line)
  32. 	slope = (line[1][1] - line[0][1]) / (line[1][0] - line[0][0])
  33. 	y_intercept = line[0][1] - (slope * line[0][0])
  34. 	return [slope, y_intercept]
  35. end
  36. def intersection_finder(line1,line2) #finds the intersection point when given four points -- makes 2 lines, solves for x=y
  37. 	line1 += eq_maker(line1)
  38. 	line2 += eq_maker(line2)
  39. 	if line1[2] ==  line2[2] 
  40. 		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
  41. 		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
  42. 	end
  43. 	x_int = (line2[3] - line1[3]) / (line1[2] - line2[2]) #otherwise, return the intersection point (z2 - z1) /(m1 - m2)
  44. 	y_int = (line1[2] * x_int) + line1[3]
  45. 	return [x_int, y_int]
  46. end
  47. def on_both?(line1,line2,int)  #.round(3) is necessary because floats suck dick
  48. 	[line1,line2].each do |x|
  49. 		return false unless int[0].round(3) >= x[0][0].round(3) && int[0].round(3) <= x[1][0].round(3)
  50. 		y_range = [x[1][1].round(3),x[0][1].round(3)].sort
  51. 		return false unless int[1].round(3) >= y_range[0] && int[1].round(3) <= y_range[1]
  52. 	end
  53. 	return true
  54. end
  55. 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 
  56. 	@all_intersects[current_line] = []
  57. 	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)
  58. 	possibilities.each do |x|
  59. 		int = intersection_finder(current_line,x)
  60. 		if on_both?(current_line,x,int)
  61. 			@just_ints.push int
  62. 			@all_intersects[int] = [current_line,x] #every intersection has exactly 2 lines -- avoids some float problems
  63. 		end
  64. 	end
  65. 	return true
  66. end
  67. def area_totaler(point1,point2) #totals area under any straight_line segment from x axis -- rectangle + triangle
  68. 	x_range = [point1[0],point2[0]].sort
  69. 	y_range = [point1[1],point2[1]].sort
  70. 	width = x_range[1] - x_range[0]
  71. 	rect_height = y_range[0]
  72. 	triangle_height = (y_range[1] - y_range[0])
  73. 	return (rect_height * width) + (0.5 * width * triangle_height) #rect area + triangle area
  74. end
  75.  
  76. #format: [center-pos,base-length,height]
  77. triangles = []
  78. 5.times do #make random triangles
  79. 	triangles.push [(rand(5000) + 2501) / 10.0 , (rand(5000) + 1) / 10.0 , (rand(5000) + 1001) / 10.0]
  80. end
  81.  
  82. triangles.each do |x|#draw triangles
  83. 	coords = [(x[0] - (x[1] / 2)),0,	x[0],x[2],	(x[0] + (x[1] / 2)),0]
  84. 	@lines.push [[coords[0],coords[1]],[coords[2],coords[3]]]
  85. 	@lines.push [[coords[2],coords[3]],[coords[4],coords[5]]]
  86. end
  87.  
  88. @lines.sort_by! {|x| x[0][0]} #start at left -- first line = highest line
  89. @lines.each { |x| intersects(x) } #build all real intersections
  90. @just_ints.sort_by! {|x| x[0]} #sort intercepts by x, move from left to right
  91. @top_intersects.push @lines[0][0] #first point on the line is the leftmost point
  92. last_point = @lines.sort_by {|x| x[1][0]}.last[1]
  93. current_line = @lines[0] #start with leftmost line
  94.  
  95. @just_ints.each do |x| #iterate through intercepts, finding the top line
  96. 	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
  97. 		@top_intersects.push current_line[1]
  98. 		current_line = @lines[@lines.index {|z| z[0][0] > current_line[1][0]}]
  99. 		@top_intersects.push current_line[0]
  100. 	end
  101.  
  102. 	if @all_intersects[x].include?(current_line) #if the next intersect includes our line, switch lines, push intersect to top_intersects
  103. 		@top_intersects.push x
  104. 		current_line = (@all_intersects[x] - [current_line])[0]
  105. 	end
  106. 	#otherwise, if the int isn't on our line, do nothing
  107. end
  108.  
  109. @top_intersects.push last_point #add the last point after all intercepts =)
  110.  
  111. triangles.each_index do |x|
  112. 	puts "Triangle #{x+1}: center-position='#{triangles[x][0]}', width='#{triangles[x][1]}', height='#{triangles[x][2]}'"
  113. end
  114.  
  115. area = 0
  116. (@top_intersects.length - 1).times do |x| #count the total area under all sections
  117. 	area += area_totaler(@top_intersects[x],@top_intersects[x + 1])
  118. end
  119. puts "Computed area is: #{area}"
  120.  
  121. sum = 0
  122. triangles.each do |x| #sum all the triangles, for comparison
  123. 	sum += (x[1] * x[2] * 0.5)
  124. end
  125. puts "Area of all triangles, including overlap, is: #{sum}"
  126. puts "Done.  Took #{Time.new - timer} seconds."
Success #stdin #stdout 0.01s 4848KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
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.
https://ideone.com/fShc03
language:
Ruby (ruby 2.5.5)
created:
11 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!