Given a list of integer coordinates, l, with a length of at least 4, and an integer n such that n is smaller than the length of l (but at least 3), return the largest area of an n-sided polygon satisfies:

  • is simple (not self-intersecting).
  • has all the coordinates of its n vertices in the list l.
  • has no three consecutive collinear vertices.

Note that the polygon given in the input should comply to the three points above as well.

Test Cases

Here are a few test cases:

[(0,0), (0,-1), (-1,-1), (-1,0)], 3 -> 0.5
[(0,0), (1,0), (2,1), (2,2), (1,3), (0,3), (-1,2), (-1,1)], 3 -> 3
[(0,0), (1,0), (2,1), (2,2), (1,3), (0,3), (-1,2), (-1,1)], 5 -> 5.5
[(0,0), (1,0), (2,1), (2,2), (1,3), (0,3), (-1,2), (-1,1)], 6 -> 6

You can try any test cases you like here.

Make your code as short as possible.


closed as unclear what you're asking by Anders Kaseorg, Rɪᴋᴇʀ, Wheat Wizard, FantaC, Steadybox Jan 12 '18 at 0:31

Please clarify your specific problem or add additional details to highlight exactly what you need. As it's currently written, it’s hard to tell exactly what you're asking. See the How to Ask page for help clarifying this question. If this question can be reworded to fit the rules in the help center, please edit the question.

  • \$\begingroup\$ This is a good challenge, but I would probably include some test cases in the body. Also, may we assume that no 3 points are collinear? \$\endgroup\$ – Giuseppe Dec 29 '17 at 20:31
  • \$\begingroup\$ @Giuseppe What test cases would be useful? \$\endgroup\$ – 0WJYxW9FMN Dec 29 '17 at 20:34
  • \$\begingroup\$ I'd just pick a few at random, including one where n is small but |l| is much larger. The link to generate more test cases is useful for getting more should we need them. I don't have any good insight on this problem, other than that the likely algorithms are going to be the brute force O(|l|^n) \$\endgroup\$ – Giuseppe Dec 29 '17 at 20:37
  • 1
    \$\begingroup\$ When you say the input coordinates are in anticlockwise order, does this imply that they are vertices of a convex polygon, i.e. all of them lie on the border of their convex hull? \$\endgroup\$ – xnor Dec 29 '17 at 21:02
  • 1
    \$\begingroup\$ Your test program only considers polygons made from sequences of vertices in the given order, even if another order may yield a larger area. Also, it fails to exclude self-intersecting polygons, for which the shoelace formula may over- or under-count some regions depending on the winding number around them (how should self-intersecting polygons be handled?). \$\endgroup\$ – Anders Kaseorg Jan 6 '18 at 0:02

Python 2, 172 bytes

-1 byte thanks to J843136028

bug fix thanks to Jonathan Frech

from itertools import*
def f(l,n,L=()):
 for p in combinations(l,n):
  for i in range(n):r+=(p[j][0]+p[i][0])*(p[j][1]-p[i][1]);j=i
 print max(L)

Try it online!

  • \$\begingroup\$ On the fourth line, you could do r,j=0,-1. On the sixth line, you could do L+=abs(r/2.),. \$\endgroup\$ – 0WJYxW9FMN Jan 11 '18 at 17:17
  • \$\begingroup\$ @J843136028 r,j=0,-1 doesn't save any bytes compared to r=0;j=-1, but thanks for your other suggestion. \$\endgroup\$ – nog642 Jan 11 '18 at 20:13
  • \$\begingroup\$ Your test cases only work because they are in increasing order (TIO). \$\endgroup\$ – Jonathan Frech Jan 12 '18 at 17:13
  • \$\begingroup\$ A proposed fix would be not to use a mutable object for your L default. Using a tuple instead of a list makes the function truly reusable (TIO). \$\endgroup\$ – Jonathan Frech Jan 12 '18 at 17:16
  • \$\begingroup\$ @JonathanFrech Right, I forgot python functions save mutable default arguments between calls. Thanks. \$\endgroup\$ – nog642 Jan 12 '18 at 17:47

Not the answer you're looking for? Browse other questions tagged or ask your own question.