Undergrad Area divided by linear function

[YoungPhysicist]

The original problem for anyone that can read Chinese:
https://zerojudge.tw/ShowProblem?problemid=b221
The problem defines a convex polygon with multiple points located in the first quadrant and the required task is to find a linear function y = ax that can spilt the polygon into two parts each with the same area.(The “a” can be within the accuracy of 0.02 from the actual answer,see why in a second)

Since this is actually a program question (Like the ones on Project Euler or UVa) so I originally wrote a program that basically tries every possible a value from y-axis to x-axis(via survey formula),but my program fail to finish in the time limit,so I think this problem may require some math insight which I don’t have.

Are there any suggestions on how this might have been done?Since it leaves a space for error,does it has something to do with calculus?

 

[mfb]

The two areas are monotone with respect to the angle of your straight line: Increase the angle relative to the x-axis and the upper area will never increase while the lower area will never decrease. Instead of trying everything you can find the optimal solution iteratively.

You also don't have to recompute the area each time, extrapolating from the previous value should work reasonably well once you are somewhat close to the solution.

 

[Mark44]

The problem defines a convex polygon with multiple points located in the first quadrant and the required task is to find a linear function y = ax that can spilt the polygon into two parts each with the same area.(The “a” can be within the accuracy of 0.02 from the actual answer,see why in a second)

Since this is actually a program question (Like the ones on Project Euler or UVa) so I originally wrote a program that basically tries every possible a value from y-axis to x-axis(via survey formula),but my program fail to finish in the time limit,so I think this problem may require some math insight which I don’t have.

First, it's not possible to try "every possible a value," since a is a real number, and there are uncountably many of them. However, if you're writing a computer program, there are only a finite number of floating point values between any two adjacent integers, due to the limited storage used by floating point numbers. It would be possible to check all of the floating point values for a between, say 0 and 1, but it would take some time to do this.

Second, I don't understand what you are saying here: "a program that basically tries every possible a value from y-axis to x-axis..." The equation of the line is $y = ax$, so it crosses the x and y axes at the origin and nowhere else. The line y = ax does not cross from the x-axis to the y-axis.

How I would solve the problem:
1. Calculate the area A of the polygon, using Heron's formula (do a web search if you don't know it)
2. Determine the smallest value of a so that the line y = ax intersects the polygon only at a corner point
3. Increment a by some fixed amount
4. Find the two points on the polygon at which the current line y = ax intersects the polgon
5. Find the area of either part of the intersected polygon
6. If the area you found equals A/2 (or is close enough), then stop.
7. Otherwise, go to step 3.

 

[mfb]

Faster: Find the smallest and largest value of a for an intersection (let's call them B and C). Take the average (or the average angle - a bit more time-consuming to calculate but gives a better result) D, check which area is larger (if we are not within the tolerance yet), consider (B+D)/2 or (C+D)/2 as next value for a, depending on which side was larger. Repeat, reducing the remaining search space by a factor 2 each time.

Even faster: Do some interpolation instead of simple averages. As an example, if the upper area was 55% of the total area, we are probably quite close to the target value already and should search closer to that number.

 

[YoungPhysicist]

@mfb and@Mark44:
My point is that I make the program to try the a value from 0.02 all th way to 100 with every 0.02 as a step,that is good enough for this case,sorry for the mistake above

 

[mfb]

I thought that was too slow?

but my program fail to finish in the time limit

Steps of 0.04 would be sufficient, by the way.

 

[YoungPhysicist]

I thought that was too slow?

Yeah,that’s why I post the problem on this forum

 

[mfb]

Then why do you say it is good enough in post 5?

 

[YoungPhysicist]

Cause the time limit for the test point is 2 seconds and each testppint have 40 to 50 polygons to deal with in a row,and my original program takes 1 second per polygon,which clearly won’t make it.