# Determine Circles

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.

## Explanation

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.

## Rules

• 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.

## Scoring

Golf your way to the shortest code!

• @tsh the points maybe same (question edited to solve this problem)
– okie
Commented Apr 13, 2021 at 6:44
• This is a minimum set cover problem, where identifying each set involves calculating the circumcenters of triangles. Commented Apr 13, 2021 at 7:02
• @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... Commented Apr 13, 2021 at 10:07
• Will there be fewer than 3 points?
– att
Commented Apr 13, 2021 at 23:00
• @att yes, there will be any amount of points.
– okie
Commented Apr 14, 2021 at 0:04

minimum.map g.permutations.nub
g[]=0
g(p:q:r)=1+g(snd$span(p#q$r!!0)r)
g _=1
(a#b)c d|t<-c!a?j(b!a)=t!!1/=0&&b!d?t?j(c!d)!!1==0
j[x,y]=[x,-y]
[x,y]?[z,t]=[x*z-y*t,x*t+y*z]
(!)=zipWith(-)
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.

## How?

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.

CircleThrough@#/.{_@{_.,_.}|_Circle:>1,_:>Min[#+Reverse@#&[#0/@Subsets[#][[2;;-2]]]]}&


Try it online!

• 86 bytes
– att
Commented Nov 8, 2021 at 4:26