language: Ruby (ruby-1.9.3)
date: 201 days 10 hours ago
link:
visibility: public 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126

=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."