18
\$\begingroup\$

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

Task

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!

\$\endgroup\$
6
  • \$\begingroup\$ @tsh the points maybe same (question edited to solve this problem) \$\endgroup\$ – okie Apr 13 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 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\$ – Dominic van Essen Apr 13 at 10:07
  • \$\begingroup\$ Will there be fewer than 3 points? \$\endgroup\$ – att Apr 13 at 23:00
  • \$\begingroup\$ @att yes, there will be any amount of points. \$\endgroup\$ – okie Apr 14 at 0:04
5
\$\begingroup\$

Haskell, 252 203 bytes

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.

\$\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.