PROBLEM LINKS :
Author : Yash Mehta
Tester : Raghu Raman
Editorialist : Yash Mehta
DIFFICULTY:
MEDIUM-HARD
PREREQUISITES:
Mathematical generalizations, observation, geometry
PROBLEM:
A man walks a simple smooth curve starting and ending at the same point. Simple curve means his path does not intersect itself anywhere. When he returns to his starting point, he is walking in the opposite direction in which he started. His dog runs parallelly to him at a distance of 0.25 to his right. We need to find how much distance does the dog travel more than the man. The man’s path passes through N specified points in the given order.
EXPLANATION:
A simple way of looking at this is doing an instantaneous analysis of an infinitesimal section of the path. Consider an infinitesimally small arc (remember, path is smooth, hence any infinitesimal section of the path will always be an arc) which covers an angular displacement of d\theta around it’s centre (wherever that may be, doesn’t matter). Let the man be running on this arc be in a counter-clockwise orientation. Around the same centre, covering the same angular displacement will be the dog. Hence the “infinitesimal difference in distance covered” will be 0.25d\theta. If we sum this up over the entire length of the path, since this 0.25 remains constant, it will essentially become 0.25 times “net angular change experienced by the tangential vector of the path of the man”.
Naturally, if the path of the man is overall anti-clockwise in orientation, the dog would have travelled more than the man. Since it is given that the man returns running in the opposite direction as compared to when he started, one could assume that the net angular change (magnitude) experienced by the tangential vector of the man’s path is \pi. So the differences in the distances would be 0.25\pi if the curve is overall anticlockwise in orientation and -0.25\pi if the curve is overall clockwise in orientation.
However, as it turns out, there may also be a path that gives the net angular change of the tangential vector as 3\pi (refer to this link for clarity). Hence, the answer would be either 0.25\pi or 0.75\pi if the path is anti-clockwise and either -0.25\pi or -0.75\pi is the path is clockwise.
The difference in distances can NOT be 5(0.25)\pi and so on because the curve never intersects itself (if it did, it is easy to find such a path which would give you such results)
In any case, the actual difference in distance is not asked. Taking the sine of the answer would result in 0.707 or -0.707 depending on the orientation of the curve.
How to find the orientation of the curve? Since the man follows a smooth curve passing through the N specified points, naturally, if the N points in the given order are in anti-clockwise orientation, then the man’s path too would be overall anti-clockwise (regardless of whatever deviations you make him go through in between any 2 points, check this for yourself (a non self-intersecting curve again ensures this)).
The orientation of the curve can be found by summing up (x[i] - x[i-1])*(y[i] + y[i-1]) over all points in cyclic fashion. If the sum is positive, the orientation is clockwise.
Refer this link for further reading on why this method of finding the orientation of N given points using this algorithm actually works.
In conclusion, sum up (x[i] - x[i-1])*(y[i] + y[i-1]) over all points in cyclic fashion. If the sum is negative, print 0.707, else print -0.707.
This is the link to the correct code.
NOTE:
The original problem was not intended to be like this. Originally, I wanted to ask the difference in distances, given different values of spacing (instead of fixing it as 0.25). The fact that it can also be 3D\pi and not just D\pi had eluded my sight till the very last moment and I was forced to make a few changes in the problems.
However, I hope you take this in the spirit of learning and not scoring points and enjoy the curious simplicity yet difficulty of this problem. I am in process of uploading a few links that will provide you further reading on this problem. This problem is actually purely a mathematical one, converted into the domain of competitive programming. There are very interesting facets to this problem.
Original source : “Dr. Euler’s Fabulous Formula” by Paul J. Nahin