This is a follow up on http://yetanothermathprogrammingconsultant.blogspot.com/2010/03/looks-difficult-to-me.html
I tried a simple minded MINLP formulation, and solved this with Baron:
This actually worked! Even for n=100 and n=200. Note that it is important to use a global solver as there are many inferior local solutions. As I solved with OPTCR=0 these are really proven global optimal solutions. I assumed the rectangle can not be rotated and must be aligned with the x and y axes. Here are some results.
Here are the corresponding plots of the solutions:
Of course faster special purpose algorithms exist for this problem.