yashi's blog

Help In A Simple Geometry Problem
By yashi, history, 9 years ago, In English

Hello Codeforces,

Recently I decided to start learning geometry so I found out that I have to start with the simple geometry, basic shapes, basic laws and cakewalk problems to set off my journey with geometry and computational geometry then, so I came across this problem from the gym,

Given a circle (the center of the circle |x|,|y| <= 1000, and the radius r <= 10000) .
Given a rectangle (the coordinates of the bottom-left corner and the upper-right corner, |x|,|y| <= 1000 as well) .
It's guaranteed that the upper-left corner of the rectangle is inside the circle, the width and the height of the rectangle are longer than 2.r .
you're to calculate the area of the intersection between the circle and the rectangle .

Here's what I did :



- Obtain the two lines P2-P3 let's say L1 and P2-P1 let's say L2 .
- Find the points of the intersection between the lines L1,L2 and the the circle, They're CL1, CL2 .
- Compute the angle (CL1 C CL2) theta .
- Compute the area of the circular sector determined by theta, say A .
- Subtract the area of the triangle (CL1 C CL2) from A .
- Add the area of the triangle (CL1 P2 CL2) to A and A is the answer .

So I keep getting WA for the couple past days. Since it's being the first time I write a geometry code I know it'd be so buggy and really it was, I've been debugging it for hours and I re-wrote it several times, and eventually I had no thing to do with it, I badly ran out of my shots :(
Here's my code .

It would be really appreciated if someone tells me what's going wrong (maybe it's my algorithm though, Now I doubt it's absolutely correct) Thanks in advance .

By the way, any advice, references, and problems would help a noob to kick-off in geometry would be highly appreciated as well .

  • Vote: I like it
  • +2
  • Vote: I do not like it

»
9 years ago, # |
  Vote: I like it +1 Vote: I do not like it

I solved this using calculus (if you want another alternative).

First, translate the center of the circle to the origin. Since the integral can be interpreted as an area we are going to separate the circle in half (below the x axis and above the x axis) and get the areas from them.

A good thing to notice is that, by symmetry, if the line L1 is above the x-axis the area you're going to sum above the x-axis is the same area you would subtract if L1 was below the x-axis (for calculating the area, below of the x-axis, of the circle and subtracting that from the rectangle with rounded border).

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

    It's really a nice approach.

    I'd be so grateful if you could elaborate more on how did you come with function you integrate.

    → Reply
    • »
      »
      »
      9 years ago, # ^ |
      ← Rev. 3   Vote: I like it 0 Vote: I do not like it

      I will solve for this drawing but the other configurations are similar. The blue + white area needed are subtracted instead of added from the orange one when the rectangle doesn't have points above the x-axis.

      The circle equation is just

      the plus sign is for the part above the x-axis, the negative for the part below the x-axis. Find the points P1 and P2 and then integrate the circle equation from x = P1 (or P2) to x = r to get the needed white (orange) area. The blue area for the rectangle is straightforward.

      To solve the integral we can make a trigonometric substitution, a possible one is x = rsin(θ) and integrate θ instead of x.

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

        Thank you .

        That was very useful and helpful
        I do appreciate your help :D .

        → Reply
»
9 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

UPD(deleted): It does not refer to this problem.

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

    The upper-left corner of his farm is inside the well.
    The width and the height of the farm are bigger than Diameter (2R) of the well.

    from the problem statement. I think the problem setter made these constraints to make the problem easier and evade such tricky cases, as the problem states I think it will always be just two intersection points .

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

      Oh i missed this "rectangle are longer than 2.r"

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

Any other solutions beside calculus ??

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

move the circle to the position where its center is (0,0) and move the rectangle to the corresponding position. using atan2/atan will makes the problem easier to solve.

→ Reply