5
\$\begingroup\$

And then the King said: You fought bravely, Knight, and your deed will not be forgotten for centuries. For your valor I grant you this castle and the lands around it. Things rush me, and I can not take you to the castle. Therefore, I will give you the way from this place to the castle. Now go and come back after the deadline. - as it is written in the Green Book of Years.

In addition, it is known from the Green Book of Years that the lands with which the castle was granted were in the shape of a circle. The king was very wise and, in order to avoid unnecessary proceedings regarding the right to land, always granted only areas of land on the map that have a convex shape.

Recently, historians have had information about where the castle was located and where this historical conversation took place. They want to know how much land did the Knight get on the assumption that the road to the castle was perfectly straight.

Explanation

The following figure shows in light gray the territory originally granted to the knight, and in dark gray, the one that came to him as a result of the king giving him the way.

Input

The first line of the input contains two floating-point numbers: xk and yk - the coordinates of the place where the dialogue took place. The second line contains three floating-point numbers: xc, yc and rc - the coordinates of the castle and the radius of the circle that bounds the land granted with it.

Output

Print one floating-point number - the area of ​​the land obtained by the Knight, with an accuracy of at least three characters after the decimal point.

Tests

Input    Output

2 5       5.69646
2 1 1


3 9       80.7130
2 3 5


1 3       3.141
1 2 1



Note: A triangle may not include the entire semicircle if it is too close to the center, as in the test I have given.

\$\endgroup\$
  • 4
    \$\begingroup\$ Hi there! Please consider using The Sandbox for your challenges. I've read this several times and I'm not sure what area we're supposed to find. The dark grey? The light grey? The sum of those regions? \$\endgroup\$ – Giuseppe Aug 23 at 13:53
  • 5
    \$\begingroup\$ Please also avoid excessively long backstories. In this case, because the challenge refers back to the backstory, it actually hinders your challenge. :-( \$\endgroup\$ – Giuseppe Aug 23 at 13:55
  • 1
    \$\begingroup\$ Can you please provide examples with a radius unequal to 1? \$\endgroup\$ – Jitse Aug 23 at 14:51
  • 1
    \$\begingroup\$ Also, the triangle will never, ever include the entire semicircle, unless the radius is infinite, which it cannot be. \$\endgroup\$ – Jitse Aug 23 at 15:08
  • 4
    \$\begingroup\$ Why is the outcome of the third test case not 3.141? \$\endgroup\$ – Joel Aug 23 at 19:43
7
\$\begingroup\$

Wolfram Language (Mathematica), 51 bytes

Area@ConvexHullMesh[CirclePoints[##2,7!]~Append~#]&

Try it online!

                    CirclePoints[##2,7!]            (* generate 5040 points on the perimeter of the circle *)
                                        ~Append~#   (* append the point at the end of the way, *)
Area@ConvexHullMesh[                             ]& (* and find the area of the convex hull of those points *)
\$\endgroup\$
6
\$\begingroup\$

JavaScript (ES7), 76 bytes

Port of Jitse's answer.

with(Math)f=(X,Y,x,y,r,h=hypot(X-x,Y-y))=>r*(r*(PI-acos(r/h))+(h*h-r*r)**.5)

Try it online!

\$\endgroup\$
  • \$\begingroup\$ I borrowed your argument names for clarity \$\endgroup\$ – Jitse Aug 23 at 14:46
  • 7
    \$\begingroup\$ @Jitse Sounds fair enough since I borrowed your entire logic. :p \$\endgroup\$ – Arnauld Aug 23 at 14:48
  • \$\begingroup\$ Friendly reminder that I made a mistake in the calcualtion of the triangle's area. It worked because the radius in the example is 1. \$\endgroup\$ – Jitse Aug 23 at 14:55
  • \$\begingroup\$ @Jitse Thanks. :) \$\endgroup\$ – Arnauld Aug 23 at 15:03
  • \$\begingroup\$ It's been a while but +1 for with - always +1 for with! \$\endgroup\$ – Shaggy Aug 24 at 0:35
5
\$\begingroup\$

Python 3, 107 bytes

from math import*
def f(X,Y,x,y,r):d=hypot(X-x,Y-y);return(r>d)*pi*r*r or(pi-acos(r/d))*r*r+(d*d-r*r)**.5*r

Try it online!

-3 bytes thanks to Arnauld

-4 bytes thanks to squid

-5 bytes thanks to Greg Martin

Explanation

First, we calculate the traveled distance between both coordinates using the Pythagorean theorem. Let's call it d.

Then, we construct a rectangular triangle between coordinate 1, coordinate 2 and the point on the circle where it meets with the straight line. Using the Pythaogrean theorem again, the area of this triangle is given by $$\frac{1}{2}\times\sqrt{d^2-r^2}\times r$$ where d is the distance between the coordinates and r is the radius of the circle. Since we have two of those triangles, this area is resembled in the code by (d*d-r*r)**.5*r

Next, we need to calculate the remaining area of the circle. A circle's area is given by $$ a = \pi\times r^2$$ However, part of the circle is already taken into account. The angular fraction of the circle that is already described by the triangles is given as $$\cos^{-1}(r/d)$$ so that the remaining area in the circle can be described by (pi-acos(r/d))*r*r.

And then some code juggle to make it as short as possible.

Except...

when the traveled distance lies within the circle. Then just return the circle area.

\$\endgroup\$
  • \$\begingroup\$ I think you forgot the case, when X-x and Y-y are 0. In this case, there is division by zero. \$\endgroup\$ – Ver Nick says Reinstate Monica Aug 23 at 15:01
  • \$\begingroup\$ @VerNick Ah yes, you're right. It fails if the traveled distance lies within the circle. Fixed now. \$\endgroup\$ – Jitse Aug 23 at 15:07
  • \$\begingroup\$ BTW, a very good explanation, might be useful for those code golfers, that are not very good with geometry ;-) \$\endgroup\$ – Ver Nick says Reinstate Monica Aug 23 at 17:11
  • 1
    \$\begingroup\$ Shouldn't it be r*r>d rather than r>d? \$\endgroup\$ – Joel Aug 23 at 18:39
  • \$\begingroup\$ If you change acos(r/d**.5) to acos(max(1,r/d**.5)) (if that's the right syntax), then you don't need to or the return computation at all ... this saves 8 bytes or so. I don't know whether this works when d=0; if there's an arcsecant function, it can be applied to d**.5/r to get around this. \$\endgroup\$ – Greg Martin Aug 24 at 3:10
4
\$\begingroup\$

Jelly, 33 bytes

½÷@ÆAØP_ײ}
I²SḢ_²}½×ʋ+çɗṛ²×ØPʋ>?

Try it online!

Port of @jitse’s Python answer so be sure to upvote that one! A full program taking as its arguments [[xk, xc], [yk, yx]] and r.

\$\endgroup\$
3
\$\begingroup\$

Python 3, 96 bytes

from math import*
def f(X,Y,x,y,r):t=max(hypot(X-x,Y-y)**2/r/r-1,0)**.5;return(t-atan(t)+pi)*r*r

Try it online!

In Python 3.8, the solution can be further improved using assignment expressions:

Python 3.8 (pre-release), 91 bytes

lambda X,Y,x,y,r:((t:=max(hypot(X-x,Y-y)**2/r/r-1,0)**.5)-atan(t)+pi)*r*r
from math import*

Try it online!

-2 bytes thanks to @Jitse

This solution is based on a bit more math manipulation of the formula. Let \$\theta\$ be the size of common angle of each triangle and its corresponding sector. The area of each triangle equals to \$\frac{1}{2}\times r\tan{\theta}\times r\$ and the area of the common sector of the triangles and the circle equals to \$\theta\times r\times r\$. Hence, the total area $$S=\tan{\theta}\cdot r^2 +\pi r^2-\theta r^2=(\pi+\tan{\theta}-\theta)r^2$$

We define \$t\$ to be $$t=\tan{\theta}=\frac{\sqrt{d^2-r^2}}{r}=\sqrt{\frac{d^2}{r^2}-1}$$ Here, \$d\$ is the distance between the two given coordinate pairs. Then we have $$S=(\pi+t-\arctan{t})r^2$$

\$\endgroup\$
  • \$\begingroup\$ Welcome to Codegolf! You have a nice approach to this problem. It is very clear and consise. Since your lambda function is not recursive, you can make it anonymous and save 2 bytes like so: Try it online! \$\endgroup\$ – Jitse Aug 24 at 9:07
  • \$\begingroup\$ @Jitse Thanks for the suggestion. The rules here are unclear to me and I cannot find the answer about this in other posts. I understand that one-line solutions using lambdas are accepted because the whole code block returns a function that can be applied to the arguments (i.e. (#code#)(arg1, ...)). However, when the program has multiple lines, the whole code block can no longer be used as a single function. In this case, do the returned functions need to be named (for later reuse) or not? \$\endgroup\$ – Joel Aug 24 at 10:56
  • \$\begingroup\$ As long as you make the import statement before defining your function, it can still be called using (lambda s: [do something])(s). Therefore, the consensus is that it is still valid to leave it anonymous, so long as you don't need to refer to it from within your core code. In this case, you only need to name it to demonstrate its functionality. Due to the way that TiO counts characters, the easiest approach is to define the funtion name in the header and import other stuff afterwards. For demonstration purposes, it doesn't really matter. \$\endgroup\$ – Jitse Aug 24 at 11:08
  • \$\begingroup\$ You can find more basic golfing rules for Python here and in other meta threads. \$\endgroup\$ – Jitse Aug 24 at 11:09
  • \$\begingroup\$ Thanks much for the clarification. I've updated the answer. \$\endgroup\$ – Joel Aug 24 at 11:23
1
\$\begingroup\$

C (clang), 111 103 93 bytes

float f(X,x,r)_Complex X,x,r;{X=cabs(X-x)/r;return(4*atan(1)-atan(X=csqrt(X*X-1))+X)*r*r;}

Try it online!

It's 90 bytes for the code, but +3 bytes because we need to pass -lm to the compiler.

Thanks to @ceilingcat for shaving off 12 bytes, and the brilliant use of csqrt() inspired me to take the coordinates as complex numbers, to shave off another 10 bytes.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.