Count the number of distinct circles through at least three grid points in a square grid; see http://math.stackexchange.com/questions/273348.

Question273348.java

import java.util.HashSet;
import java.util.Set;

public class Question273348 {
    public static long gcd (long p,long q) {
        if (p < 0)
            p = -p;
        if (q < 0)
            q = -q;

        if (p < q) {
            long tmp = p;
            p = q;
            q = tmp;
        }

        if (q == 0)
            return p;

        for (;;) {
            long r = p % q;
            if (r == 0)
                return q;
            p = q;
            q = r;
        }
    }

    static class Circle {
        long x;
        long y;
        long r2;
        long den;

        public Circle (long x,long y,long r2,long den) {
            this.x = x;
            this.y = y;
            this.r2 = r2;
            this.den = den;
        }

        public boolean equals (Object o) {
            Circle c = (Circle) o;
            return c.x == x && c.y == y && c.r2 == r2 && c.den == den;
        }

        public int hashCode () {
            return (int) (x ^ (y * 31) ^ (r2 * 37) ^ (den * 43));
        }
    }

    public static void main (String [] args) {
        for (int n = 1;;n++) {
            Set<Circle> circles = new HashSet<Circle> ();
                    
            for (int x1 = 1;x1 <= n;x1++)
                for (int y1 = 1;y1 <= n;y1++)
                    for (int x2 = 1;x2 <= x1;x2++)
                        for (int y2 = 1;y2 <= n;y2++)
                            for (int x3 = 1;x3 <= x2;x3++)
                                for (int y3 = 1;y3 <= n;y3++) {
                                    long ax2 = 2 * (x2 - x1);
                                    long ay2 = 2 * (y2 - y1);
                                    long ax3 = 2 * (x3 - x1);
                                    long ay3 = 2 * (y3 - y1);
                                    long den = ax2 * ay3 - ax3 * ay2;
                                    if (den == 0) // line
                                        continue;
                                    long b2 = x2 * x2 + y2 * y2 - x1 * x1 - y1 * y1;
                                    long b3 = x3 * x3 + y3 * y3 - x1 * x1 - y1 * y1;
                                    long x = b2 * ay3 - b3 * ay2;
                                    long y = ax2 * b3 - ax3 * b2;
                                    long gcd = gcd (gcd (x,y),den);
                                    if (den < 0)
                                        gcd = -gcd;
                                    x /= gcd;
                                    y /= gcd;
                                    den /= gcd;
                                    long dx = x - den * x1;
                                    long dy = y - den * y1;
                                    long s = dx * dx + dy * dy;
                                    circles.add (new Circle (x,y,s,den));
                                }
            System.out.println (n + " : " + circles.size ());
        }
    }
}