fastnoise's blog

Some help with this geometry problem...
By fastnoise, history, 8 years ago, In English

A few days ago I read this problem, it seem like a easy geometry problem about optimization over the angles, so I used ternary search to rotate the point about the origin, like the picture show, but I got WA, so, any idea about what's my error? ****

Rotating the point

Thank you very much.

  • Vote: I like it
  • 0
  • Vote: I do not like it

Comments Comments (4)
| Write comment?
»
8 years ago, # |
← Rev. 4   Vote: I like it 0 Vote: I do not like it

Hi. I didn't try to submit a solution to your problem. But I will say how would I proceed if I were to solve it. Instead of doing a ternary search I would do a binary search (the function that computes the surface is increasing) with an epsilon error from 0 to pi by solving the following equation A ~ S-T (I compare A with A1), where S is the area of the sector and T is the area of the triangle formed by the chord. When I find this angle I would try to find the distance from P to OX, let's note it H (It's basically the height of the triangle) (that would be my y) and then I would generate the distance from the point (R,0) to H so I will have my x coordinate. I guess my idea is very similar to yours and I think this is the way to solve the problem. Sorry for my bad formatting and I hope it helps. In order to optimize the solution I would just lower my epsilon error.

→ Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I couldn't understand completely your idea, may be because of the format you wrote it, but my idea is very similar, a make ternary search over the [0; pi] iterval, and I try to minimize f( angle ) — K, this is the fundamental part of the code I submited, if you se any error or suggestion I would be grateful:

    public Point _solve(){
			
			double l = 0;
			double r = Math.PI;
			x = R;
			y = 0;
			for( int i = 0; i < 300; ++i ){
				double m1 = l + ( r - l ) / 3;
				double m2 = r - ( r - l ) / 3;
				if( Math.abs( f( m2, x, y ) - K ) - Math.abs( f( m1, x, y )  - K ) >= 1e-10 )
					r = m2;
				else
					l = m1;
			}
			
			x = R * Math.cos( l );
			y = R * Math.sin( l );
			return new Point( x, y );
		}
    → Reply
    • »
      »
      »
      8 years ago, # ^ |
      ← Rev. 2   Vote: I like it 0 Vote: I do not like it

      Did you change K before calling the function _solve(), because instead of K you should have pi*r^2/(k+1)? Also I would check if I am between A1-eps and A1+eps .. in case that I find f(m1,x,y) or f(m2,x,y) that are inside this interval I stop my search and I return this result (in this case I would be reassured that there are no possible problems). My binary search would look the same but I would stop if I am inside this interval, if my middle < A1-eps => left = middle; else if middle > A1+eps right = middle else return (x,y). And I would lower eps in case that I don't find a solution. In your case I would put instead of 300, 600.

      → Reply
    • »
      »
      »
      8 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Is f(angle) a function of area? If so, how it correlates with abs(f(val) — K)?

      afkid's idea was to use the binary search in order to find the angle for which the ratio A1/A2 would be true. As the function of A1/A2 is monotonic it is convenient to use bin search. If you don't understand, you can draw some circles and chords, in order to understand this idea. I hope that you will solve this problem after drawing and rethinking of the idea.

      → Reply