# Maximum Area of a Polygon with Vertices of a Polygon [closed]

### 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.

• 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? – Giuseppe Dec 29 '17 at 20:31
• @Giuseppe What test cases would be useful? – 0WJYxW9FMN Dec 29 '17 at 20:34
• 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) – Giuseppe Dec 29 '17 at 20:37
• 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? – xnor Dec 29 '17 at 21:02
• 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?). – 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):
r=0;j=-1
for i in range(n):r+=(p[j]+p[i])*(p[j]-p[i]);j=i
L+=abs(r/2.),
print max(L)


Try it online!

• On the fourth line, you could do r,j=0,-1. On the sixth line, you could do L+=abs(r/2.),. – 0WJYxW9FMN Jan 11 '18 at 17:17
• @J843136028 r,j=0,-1 doesn't save any bytes compared to r=0;j=-1, but thanks for your other suggestion. – nog642 Jan 11 '18 at 20:13
• Your test cases only work because they are in increasing order (TIO). – Jonathan Frech Jan 12 '18 at 17:13
• 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). – Jonathan Frech Jan 12 '18 at 17:16
• @JonathanFrech Right, I forgot python functions save mutable default arguments between calls. Thanks. – nog642 Jan 12 '18 at 17:47