Same logic works in python but not in C++

general
1

This Problem: The Delicious Cake is from June Long Challenge Div 2. I’ve tried solving it using Python3.6 and got 15 Pts. with lot of TLE’s, so, I tried solving the same problem using c++. But It gives WA on some cases and TLE on others.

I’ve implemented the same logic in both but got different results. I first found the Convex hull for all points and then removed the points forming the convex hull from the original list of Points and added it to the list of all polygons, and repeated the same till all possible polygons are made. And then, for each query, I checked inside how many polygons the candle lies. I’ve also covered the case when a point lies on edge of a polygon.

C++ code
Python code

I am a beginner in C++ and don’t know how to use it properly for CP. Can anyone please tell me what’s wrong with this C++ code? Any help will be appreciated. Thanks

2

I don’t really know the solution to this problem. But my guess is that it’s your logic, and not Python, that causes TLE. For example, lines 107-108 (python):

for pts in poly:
  points.remove(pts)

This makes it easily O(n^2).

Sorry, I take this comment back lol, I should have read the problem more. I’ll look more into it

3

Sorry, I’m probably too weak in geo (and it’s quite late here) to figure this out. Phoning a friend like @everule1 for this who’s strictly better than me

4

Change #define ll long to using ll = long long int;.
Overflow here int val = (q.y - p.y) * (r.x - q.x) - (q.x - p.x) * (r.y - q.y);
Floating point equality here
distance(pt1x, pt1y, ptx, pty) + distance(ptx, pty, pt2x, pt2y)) == distance(pt1x, pt1y, pt2x, pt2y))
(Generally don’t use floating point calculations if the answer is a integer)
If you want to check if (X_2, Y_2) lies between (X_1, Y_1) and (X_3, Y_3), use
(Y_2 - Y_1) (X_3 - X_1) = (Y_3 - Y_1)(X_2 - X_1). checking if the slopes of the line from (X_1, Y_1) -> (X_2, Y_2) is equal to the slope of the line from (X_1, Y_1) -> (X_3, Y_3).
Also increase the speed of your convex hull. Use this
https://cp-algorithms.com/geometry/grahams-scan-convex-hull.html
After the initial sort, each hull will take O(N), therefore generating the hulls in O(N^2)

3 Likes
5

@everule1 Looks like there are lot of problems with my code…:sweat_smile:. Should I use long long int to avoid overflow? Thanks a lot for help @galencolin @everule1

6

ya

7

Got AC in 2 and WA in other cases…This code
I’ve also tried changing datatypes in some functions from int to long long int but still getting WA.

8

You are still using floating point values for isonline. Do not use any floating point values. The only time it’s acceptable is when the answer is a floating point value.