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)
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.
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
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.
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.
This being my first post, there’s a big yellow banner on the side suggesting comments should be constructive, and lucky for you because otherwise I’d go off on this puzzle. I joined just 2 days ago and I’m only 3 steps into the “algorithms” track, having just finished a few puzzles with “loops” (not making this up, that’s literally how they’re tagged) and 2 “medium” difficulty puzzles, one which I solved using a smidge of recursion plus eval (which wasn’t disabled so I guess it’s legit) and a supposed trig problem for which I didn’t need any trigonometric functions nor even square root from the math library. So now I’m on the next milestone which is puzzle of the week, and correct me if I’m wrong but there’s only one puzzle of the week I can be working on right now and this is it this week. Well working on it is what I’ve been doing, looking at those pretty pictures with dots and lines and painstakingly coding up a method of counting the little guys all the way around, only to find that after a bit of effort to correctly exclude the boundary and such, it works great on the examples given but times out on the other two tests. So no problem, it’s simply a slightly more complex optimization problem, and anyway I’m pretty handy with a keyboard or at least the dexterous half, so how hard could it be to get one more of countlessly many achievements, on just step 3 of the algorithm track? I optimize the sh*t out of it (sorry for swearing but I really did do a number on it), using set operations on column masks instead of looping thru each Moore neighbor, and yes getting the right answer on my machine at home but finding that it still takes a few minutes to run, only to finally come here and see that Froot Loops are for kids and the way this one has to be done, silly rabbit, is by knowing some unnamed theorem (and I mean unnamed here in the forums, while in the problem statement not so much as mentioned or hinted) making explicit use of the fact that all the vertices are integers as probably its strangest and most coincidental condition. To make the situation more of a downer in my case, I actually knew about this theorem from high school geometry, but to my memory it only worked on convex polygons, not on any simple polygon like the whack job going on in example deux. So I guess all of this is to say I’ve got a bit of a sour taste in my mouth from this experience in contrast to the otherwise very polished content on this site, and I hope that’s what was intended for me to learn my lesson about trying to figure stuff out on my own instead of asking Jon Skeet. But if not then maybe, just maybe suggest that actually counting the dots might not be the best approach, if only because this is the singlest problem that can get past that single hurdle at the moment. Thanks for listening, and regardless of how simple it turns out this is to implement (or probably worse because of how simple), I’m far too burned to care about this puzzle anymore. Maybe I’ll come back and try the one next week, we’ll see. Edit: Whatever, I’m over it, after completing in 10 lines of code with 100 lines commented out, and giving it the one full star it deserves.
It looks like I’m going to have to give on this one too. I feel like I’m trying to chase down some obscure mathematical issue instead of a programming challenge now. The Versaille test is the only one that isn’t passing.
If I floor the area functions output, I get 1 off. If I don’t floor until the end, I get 2 off.
