Linear Programming puzzle suggestion

input: N pairs of x and y point coordinates

  • points are connected with lines in given order, last is connected to first
  • points may have doubles: points with different index may have same coordinates
  • points may have z coord, but for this puzzle they should belong to same plane (i’m not sure how to extend this puzzle into 3d)

output: arrays of points that make polygons which original polygon consists of

p1x1,p1y1 … p1xN,p1yN

pMx1,pMy1 … pMxN,pMyN

  • N in answer is unique for every line and can be equal to 3 or larger, according to number of points in Mth result polygon
  • result polygons should have no internal crossings
  • result polygons should not overlap
  • visualise the result?

@CvxFous inb4 “is this homework”: yes

what is linear programming (it is not a programming):

1 Like

if you answer yes to this question, then you know that it probably isn’t a good idea to suggest it for people to do your homework. Just saying.

  1. this task was due over a year ago, and i failed it at that time
  2. i completely understand that rules of Codingame does not allow me to see the solutions of other participants

In that case it’s not really homework, so it’s fine, ‘homework’ means making other people do your work, that’s not the case here so I welcome your participation. (But since it’s not, you don’t have to precise it :slight_smile: )


Brr… Let’s not forget we are on Codingame. Your contest is probably challenging, but desperately lacks zombie/pony/robot invasion, ballistic calculations and explosions. No way I would solve this kind problem if not to counter a raid of panzers. Isn’t the original purpose of all this linear stuff after all?

1 Like

you forgot blackjack and so on

1 Like