Giving n(any amount) of points (x,y). What's the minimum amount of circles required to cross every point given?


Your program will get n (you can have n as part of input or use EOF instead) points (x,y).

The points might at same place => (x1,y1) = (x2,y2) can happen

x and y will be integer of range -10000~10000, while n, if you need it, will be integer too.

You should output an integer A which represent the minimum amount of circle needed to intersect all of the points. Those circle are not required to intersect each other.


For example: 1, 2 points will need 1 circle only to be sure that the points touch the circles boundary

but 3, 4 points may need 2 circles, or 1 (Determined by where the points are)

Basic test cases:
(10,10), (0,5), (0,0), (5,10) => 1 circle
(10,10), (5,5), (0,0), (5,10) => 2 circles
(1,1), (2,2), (5,3), (-1,5), (0,0) => 2
(0,0), (1,1), (2,2), (3,3), (4,4), (5,5) => 3 

Line are NOT considered as a circle

If there are 3 points (0,0) (5,5) (10,10). Then the answer would be 2 since those 3 points forms a line if you try to force a circle out of it.


  • Input can be taken in any convenient format.
  • Output can be in any convenient format as well. As long as it follow the input-reversed input order.
  • Standard Loopholes are forbidden.


Golf your way to the shortest code!

  • \$\begingroup\$ @tsh the points maybe same (question edited to solve this problem) \$\endgroup\$
    – okie
    Apr 13, 2021 at 6:44
  • 3
    \$\begingroup\$ This is a minimum set cover problem, where identifying each set involves calculating the circumcenters of triangles. \$\endgroup\$
    – Bubbler
    Apr 13, 2021 at 7:02
  • 3
    \$\begingroup\$ @Bubbler - although, obviously, two triangles could have the same circumcenter but different (and concentric) point-crossing circles, so just calculating the centres wouldn't be enough... \$\endgroup\$ Apr 13, 2021 at 10:07
  • \$\begingroup\$ Will there be fewer than 3 points? \$\endgroup\$
    – att
    Apr 13, 2021 at 23:00
  • \$\begingroup\$ @att yes, there will be any amount of points. \$\endgroup\$
    – okie
    Apr 14, 2021 at 0:04

2 Answers 2


Haskell, 252 203 bytes

minimum.map g.permutations.nub
g _=1
(a#b)c d|t<-c!a?j(b!a)=t!!1/=0&&b!d?t?j(c!d)!!1==0
import Data.List

Try it online!

The relevant function is minimum.map g.permutations.nub, which takes a list of points as input (each point as a list [x,y]) and returns an integer as output.

This solution uses only integer arithmetic, and therefore does not suffer from accuracy problems stemming from floating point errors.


Coming soon, after I finish golfing this and convincing myself that the formulas are right.


Wolfram Language (Mathematica), 86 bytes

-5 bytes thanks to @att.


Try it online!

  • 1
    \$\begingroup\$ 86 bytes \$\endgroup\$
    – att
    Nov 8, 2021 at 4:26

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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