3
\$\begingroup\$

Rules

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.

\$\endgroup\$
  • \$\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
0
\$\begingroup\$

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):
  r=0;j=-1
  for i in range(n):r+=(p[j][0]+p[i][0])*(p[j][1]-p[i][1]);j=i
  L+=abs(r/2.),
 print max(L)

Try it online!

\$\endgroup\$
  • \$\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.