Find the maximum possible area of a convex quadrilateral having sides of lengths 1, 4, 7 and 8.
The answer is 18.
The solution was:
The program below first assumed the order of the sides was 1, 4, 7, 8 and gave a table of values based on the diagonal of length d that forms a 1,4,d triangle on one side and a 7,8,d triangle on the other. Using Heron's formula it found and reported the total area of the two triangles:
d area
3 10.3923048454133
3.1 11.531991434954
3.2 12.2061344238333
3.3 12.7952297836777
3.4 13.3353079104165
3.5 13.8399918416733
3.6 14.3159130262041
3.7 14.7666392520934
3.8 15.1940982226548
3.9 15.5991921792037
4 15.9820811624679
4.1 16.3422997194526
4.2 16.6787659262476
4.3 16.9896925797232
4.4 17.2723713968984
4.5 17.5227411649723
4.6 17.7345111041297
4.7 17.8971929851682
4.8 17.9907751055955
4.9 17.9651470999707
5 17.3205082089688
A second part was added based on the limits of where the maximum might be reached, with an algorithm to find the maximum, by reversing direction and lowering the step size. It found:
d area
4.83735462072318 18
the first number being the diagonal length and the second the area of the quadrilateral. Being a maximum, there is probably some leeway in the diagonal that would still produce 18 as a maximum, to the accuracy presented. In other words, the full precision shown for the required diagonal might be spurious in the last few digits.
The same was done assuming the sequence of lengths was 1, 7, 4, 8:
6 11.6189500386223
6.1 13.3214198678306
6.2 14.141803585258
6.3 14.7953533594977
6.4 15.3509495089792
6.5 15.8350843469888
6.6 16.2609629507357
6.7 16.6359510958866
6.8 16.9642896903456
6.9 17.2482775737649
7 17.4888276901116
7.1 17.6857111170788
7.2 17.8376041159642
7.3 17.9419629485811
7.4 17.994682555401
7.49999999999999 17.989393955835
7.59999999999999 17.9160223565384
7.69999999999999 17.7575330763273
7.79999999999999 17.4810951133971
7.89999999999999 17.0038514036763
7.99999999999999 15.49193383087
The resulting maximum area was again 18, with the diagonal shown as below, forming a 1,7,7.44208406527998 triangle and a 4,8,7.44208406527998 triangle:
7.44208406527998 18
It was determined then that the answer is indeed 18 regardless of the order of the sides by verifying for 1,4,8,7:
3 10.3923048454133
3.1 11.531991434954
3.2 12.2061344238333
3.3 12.7952297836777
3.4 13.3353079104165
3.5 13.8399918416733
3.6 14.3159130262041
3.7 14.7666392520934
3.8 15.1940982226548
3.9 15.5991921792037
4 15.9820811624679
4.1 16.3422997194526
4.2 16.6787659262476
4.3 16.9896925797232
4.4 17.2723713968984
4.5 17.5227411649723
4.6 17.7345111041297
4.7 17.8971929851682
4.8 17.9907751055955
4.9 17.9651470999707
5 17.3205082089688
4.83735464639719 18
There's a slight variation in the setting up of the homing in on the maximum, as I realized by this time I was not really using the hgh variable, and also didn't need such an accurate starting point, low.
DefDbl A-Z
Dim crlf$, side(4)
Private Sub Form_Load()
Form1.Visible = True
Text1.Text = ""
crlf = Chr$(13) + Chr$(10)
side(1) = 1
side(2) = 4
side(3) = 7
side(4) = 8
For diag = side(2) - side(1) To side(2) + side(1) Step 0.1
DoEvents
s = (side(1) + side(2) + diag) / 2
a1 = Sqr(s * (s - side(1)) * (s - side(2)) * (s - diag))
s = (side(3) + side(4) + diag) / 2
a2 = Sqr(s * (s - side(3)) * (s - side(4)) * (s - diag))
Text1.Text = Text1.Text & diag & Str(a1 + a2) & crlf
Next
low = 3.9: hgh = 4.1: st = 0.01
diag = low
Do
s = (side(1) + side(2) + diag) / 2
a1 = Sqr(s * (s - side(1)) * (s - side(2)) * (s - diag))
s = (side(3) + side(4) + diag) / 2
a2 = Sqr(s * (s - side(3)) * (s - side(4)) * (s - diag))
prev = a
a = a1 + a2
If a > prev Then
diag = diag + st
Else
If a = prev Then Exit Do
st = -st / 5
diag = diag + st
End If
Loop
Text1.Text = Text1.Text & crlf & diag & Str(a) & crlf & crlf
side(1) = 1
side(2) = 7
side(3) = 4
side(4) = 8
For diag = side(2) - side(1) To side(2) + side(1) Step 0.1
DoEvents
s = (side(1) + side(2) + diag) / 2
a1 = Sqr(s * (s - side(1)) * (s - side(2)) * (s - diag))
s = (side(3) + side(4) + diag) / 2
a2 = Sqr(s * (s - side(3)) * (s - side(4)) * (s - diag))
Text1.Text = Text1.Text & diag & Str(a1 + a2) & crlf
Next
prev = 0
low = 7.3: hgh = 7.6: st = 0.01
diag = low
Do
s = (side(1) + side(2) + diag) / 2
a1 = Sqr(s * (s - side(1)) * (s - side(2)) * (s - diag))
s = (side(3) + side(4) + diag) / 2
a2 = Sqr(s * (s - side(3)) * (s - side(4)) * (s - diag))
prev = a
a = a1 + a2
If a > prev Then
diag = diag + st
Else
If a = prev Then Exit Do
st = -st / 5
diag = diag + st
End If
Loop
Text1.Text = Text1.Text & crlf & diag & Str(a) & crlf & crlf
side(1) = 1
side(2) = 4
side(3) = 8
side(4) = 7
For diag = side(2) - side(1) To side(2) + side(1) Step 0.1
DoEvents
s = (side(1) + side(2) + diag) / 2
a1 = Sqr(s * (s - side(1)) * (s - side(2)) * (s - diag))
s = (side(3) + side(4) + diag) / 2
a2 = Sqr(s * (s - side(3)) * (s - side(4)) * (s - diag))
Text1.Text = Text1.Text & diag & Str(a1 + a2) & crlf
Next
low = 3.1: hgh = 4.1: st = 0.01
diag = low
Do
s = (side(1) + side(2) + diag) / 2
a1 = Sqr(s * (s - side(1)) * (s - side(2)) * (s - diag))
s = (side(3) + side(4) + diag) / 2
a2 = Sqr(s * (s - side(3)) * (s - side(4)) * (s - diag))
prev = a
a = a1 + a2
If a > prev Then
diag = diag + st
Else
If a = prev Then Exit Do
st = -st / 5
diag = diag + st
End If
Loop
Text1.Text = Text1.Text & crlf & diag & Str(a) & crlf & crlf
Text1.Text = Text1.Text & " done"
End Sub
|
Posted by Charlie
on 2016-07-03 09:40:53 |