How to solve the problem about the cut (write a program)?

Question

Programming

Task. There is a cake (square). An arbitrary number of candles are inserted into it. It is necessary to check whether it can be cut into two equal parts, so that there are no candles in one part. (You need to cut without hitting the candles).
Picture - fastpic.ru/view/67/2015/0129/6f17589820129c216cd53...
.
Not necessarily a ready-made program (it can also be in text form). At least tell me the solution algorithm.

Answer 1

altim.narod.ru/Docs/Russian/Manuals/Contests/Chapt...

Answer 2

First, check if there is a candle in the center. If there is, then obviously it is impossible (any cut that divides the cake in half passes through the center).
Then for each candle, find the direction to it from the center. In most languages, this is done by calling the atan2(y,x) function (assuming the center is at (0,0)). It returns an angle in radians between -pi and pi.
Sort the corners in ascending order: a1<=a2<=...<=an.
If an-a1 < pi-eps, then all the candles lie inside the angle less than pi, and there is a cut.
If for some ka{k+1}-ak > pi+eps, then there is an empty corner greater than pi, and there is also a cut.
Difficulties arise when an-a1 or a{k+1}-ak are very close to pi, and you need to check exactly whether the angle is greater than pi, less than, or equal to. It all depends on the cruelty of the authors of the problem.
If the numbers are given as integers, not exceeding 10^9 in absolute value, then it is enough to calculate the determinant x{k+1}*y{k}-x{k}*y{k+1}, and determine from its sign, with which side the line connecting the candles will pass from the center. The works fit into int64, and everything is simple.
If the numbers are integers and do not exceed 10^18, then things are worse. There are validation algorithms that do not go beyond int64 (a specially written Euclid algorithm), but it may be easier to use long arithmetic.
Worst of all, if the coordinates are real numbers of an arbitrary format. I'm afraid that I'll have to write my own parser here - a simple good way to reliably check that candles with coordinates, say (1.2E220, 2.7E-180) and (-2.8E200, 6.3E-200) lie strictly on one straight line passing through the center , I don't know.

Answer 3

I would decide this way: since it is necessary to cut into two equal parts, then the cutting line must pass through the center of the cake. Now we will think at what angle (slope) to cut - you can simply enumerate all 180 degrees, but there is a counterargument in the form of a test with an existing cut, on which all the candles are located, say, behind the line with an inclination of 0.9 degrees (enumeration with tenths fractions of a degree has exactly the same argument of 0.09 degrees). The second thought is that we only have a certain number of candles, let's sort out the angle of inclination by candles: we take a candle, make a cut passing to the left of it and through the center of the cake and look for the presence of candles to the left and below the cut (subtask of the relative position of the line and points on the plane ).
According to the time estimate, it turns out to solve O (N ^ 2) directly, where N is the number of candles. It is likely that the estimate can be improved to O(NlogN) by applying some structure to find points below-left.

Answer 4

You need to learn to determine on which side of the line AB lies the point T.
If Q>0, then conditionally - "on the left", if less than zero "conditionally" - on the right.

Answer 5

you need to cut in the horizon plane, leaving the blade about half the height of the cake from its upper plane