# [Community Puzzle] Flower beds

So, thanks to you all, I picked the right theorem. However, for some reason, I fail the last case before submission by 1, and I fail the second validator once I submit.

Spoilers
The vertex of the polygon are in a Deque.
I do the triangulation as follow:
— I check that I don’t accidentally cross any vertex or side, if I do, I push back the first point for the deque, and pop the first
— if the determinant of the first and second vectors is positive, I add the surface to the total surface of the polygon, then I delete the second point, making the third next to the first in the queue
— else, back to first step .
— back to first step until I only have three vertex

EDIT, Spoilers: if it’s unclear, before triangulation, I did count the number of vertex crossed by the polygon lines.

The vertices are already given with the good order, there are no cross checks to do or whatever cause determinants are signed in a way that it will automatically remove the parts that needs to be removed.
You can just sum them all and take the asbolute value in the end

The two things you need to calculate (area and border points) require you to iterate over the pairs of consecutive vertices, but you don’t have to do any structure manipulation.

If you stored them in an array V you can just consider all V[i], V[(i+1)%n] for i from 0 to n - 1.

And actually you don’t even have to store anything, for example you can just do a loop like this:

``````X0 = x = <get first x>
Y0 = y = <get first y>
for i from 1 to n - 1:
X = <get x>
Y = <get y>
<calculate what's required with x, y, X, Y>
x = X
y = Y
<calculate what's required with x, y, X0, Y0>
``````

If it’s a reply to my post, what I meant in the checking phase is, when I draw a line to triangulate, I check before that the line stays inside the polygon, and do not cross a vertex, or do not coincide with another line of the polygon.

I’m pretty sure that the border points are good, but then, since the inner points are also good for the first three checks, I don’t know what went wrong.

Edit : I still somehow fail one validator after submitting, but before that, it seemed to be some weird rounding issue.

Actually you can chose any point you want to draw your triangles from, even outside the polygon. Then just sum the determinants from this point. Usually the point 0, 0 is chosen to triangulate from, so that the vectors coordinates to build your triangles are just the vertices coordinates.
That’s the beauty of this formula with the determinants, there are no edge cases to consider, it works all the time.
Note: for other puzzles it can be a way to determine if a point is inside a polygon or not, as this formula will give positive or negative results depending on wether the chosen point is inside the polygon or not.
For rounding issues, as said above, a good idea is to compute twice what you need to compute (i.e paralellograms areas instead of triangles) and divide by 2 at the very end.

I tried that. Must admit, I like math, but this one seems like magic to me.Thanks!
I’ll still try later to implement a nice triangulation, must finish what I started.

It is not clear from the problem description whether we can assume that the vertices are listed in an order of circumference, that is if two vertices are in neighboring lines in the input, then they are connected. Otherwise, the problem is not well posed: for example, here are two possible ways to make a polygon out of the vertex set `{(1,1),(2,3),(1,5),(7,5),(7,1)}` with a different number of interior points with integer coordinates: (sorry couldn’t find a flower on diagrams.net where I made the picture) 3 Likes

In any puzzle, if you’re given the vertices of a polygon, you can always assume that the vertices are given in order.
Otherwise the polygon is not well defined.

1 Like

What theorem guys are talking about? I feel like I also want to know it. Despite I solved it just by brute force, there was a lot of annoying edge cases … so any clever theorem would be so sweet here

1 Like

I’m pretty sure that if you search “theorem integer points” it will be among the first results 2 Likes

Very cool puzzle, I started with raycast method but really not fast enough, then I was stuck for a long time with the area, until I found the solution.

Thank you!

With this theorem puzzle goes from “Hard puzzle of the week” to “clash of code” fun puzzle

There is may be some problem with accuracy in C# version. When I use int, and cast some to decimal my code can not pass one test in IDE and Submit. When I changed all numbers to decimal my code passed all Submit tests, but did not pass one (4th) in IDE.

I am so close to solving this but having a problem in my code that is trying to find the extra vertices that are not included I believe. I pass the first two tests in the ide, but then am barely off for the last two. I don’t want to give anything away here by posting my slope code that is comparing what extra points there are, so is there anyone willing for me to private message them to see if they can catch where I am going wrong?

You can send me if you want.
Everyone seems blocked by the same problem: calculating the number of the points of integer coordinates on the border.
A general advice I could give is: draw an example.
For example with A(0, 12) and B (8, 0), you get 3 additionnal points: (2, 9), (4, 6) and (6, 3).
So your edge has been cut in 4.
How could you have guessed that it would be 4 without actually computing these extra points ?

Thanks pardouin, with your advice I was able to solve it. Took me a while to get exactly what you were hinting at, but then implementing it and not trying to find every vertex did the trick.

If I `floor` the area functions output, I get 1 off. If I don’t `floor` until the end, I get 2 off.