I think there’s a misconception that many people have with this theorem, that the area has to be integer, but it’s not true, you can get half integers.
But ofc the number of inside points is integer, there are two possible cases:
the area is integer and the number of border points is even
the area ends with .5 and the number of border points is odd
So you better keep the “double” area till the end and divide the area and the number of border points by 2 “together”.
That’s not quite the issue I’m running into on mine.
I have everything typed as doubles. I get exact answers on the first two challenges. The third is off by .5, which get’s rounded down. The last one is off by 2, which flooring/rounding wouldn’t fix that.
If you don’t mind, can you have a peek at what I have?
It is quite solvable without Pick’s theorem in 40ms for worst case. Puzzles are gym for brain. It looks like You upset by wasting time trying to optimize but actually You are given the most valuable gift. All who knew theorem before starting this puzzle must envy You, because they all just got one more 15 min puzzle with 1 loop and no exercise for brain. This is the real taste of problem solving.
And Yes counting dots is definitely not the best way. There are 1000 000 among values of (x,y) pairs it means aprox 10^12 points inside… even if counting loop will be empty I dont believe it ends in 0.5s. Lets just assume we are crossing this polygon by horisontal lines and getting crossing points x1,x2,x3,x4… and then from x1 to x2 is inside polygon from x2 to x3 is outside and to sum all of them that are in theline we will just need to calc (x2 -x1) + (x4- x3) … of course there are buch of edge cases but it is still much much faster than counting dot by dot
Yeah, I was a bit upset, but it could have actually been a good problem, if I hadn’t wasted so much time trying to churn out the result. How would you solve it without using the theorem, apart from counting the dots? Is there a solution you can point me to that uses some strategy besides these?
Looks like I am the second man among all codingamers who didn’t use this theorem (I simply havent ever heard about, but it is amazing especially it’s proof). I solved it by method I described above. I found minY, maxY of this polygon. Then I crossed this polygon with horisontal lines from minY to maxY with step 1 and found for each line intersection points and order them by X coordinate. Next thought was: If line intersects polygon in several points then first (leftmost) intersection is the place where horisontal line comes “into” polygon. second point is here line comes out of poly. That means every point on this line between X1 and X2 lies inside the polygon. For example if you have square 100x100 you will get 98 horisontal lines and 2 intersection points for each lin. So Your task will be just do x2-x1 98 times instead of 10 000 checks for dots separately.
I implemented this approach and published in C#. It really works. It feats all time limits.
Thanks for that. I actually had a thought at one point along similar lines, but dismissed it maybe because I’d already started down a different path, one that did at least work on the simpler examples. I’m going to change my vote based on the fact that it really is possible to count dots, and I’d just not done it in the most elegant fashion. And also because I think a lot of my frustration should have been directed at the quest map, and not at the one and only problem it required me to complete that week. But if it’s not low, I’m not still giving this puzzle a high rating as long as there’s no warning in the description that the approach I took, when optimized, doesn’t solve it. And frankly I don’t see why that shouldn’t have passed on medium and large as opposed to gigantic test cases, especially considering it was several times more difficult to write than the easy way out.