import java.io.*; import java.util.*; /** * Solution to Symmetry * * @author vanb */ public class symmetry_vanb { public Scanner sc; public PrintStream ps; /** * Euclid's algorithm for Greatest Common Divisor * * @param a A number * @param b Another number * @return The GCD of a & b */ public int gcd( int a, int b ) { return b==0 ? a : gcd( b, a%b ); } /** * A Point, or a Spot. * * @author vanb */ public class Point implements Comparable { /** Coordinates */ public int x, y; /** * Create a Point. * * @param x X Coordinate * @param y Y Coordinate */ public Point( int x, int y ) { this.x = x; this.y = y; } /** * Create a pretty String for debugging. * * @return A Pretty String */ public String toString() { return "[" + x + "," + y + "]"; } @Override /** * Compare this point to another, sorting on X coord, then Y coord. * * @param p Another point * @return The usual for compareTo */ public int compareTo( Point p ) { int diff = x - p.x; if( diff==0 ) diff = y - p.y; return diff; } } /** * A Line, with the equation a*x + b*y = c * * @author vanb */ public class Line implements Comparable { /** Equation coefficients */ public int a, b, c; /** * Create a Line with the equation a*x + b*y = c. * * @param a X coefficient * @param b Y coefficient * @param c Constant */ public Line( int a, int b, int c ) { // We need to normalize a, b and c so we can compare them. // Start by reducing them. int g = gcd( Math.abs(a), gcd( Math.abs(b), Math.abs(c)) ); a /= g; b /= g; c /= g; // Force the first non-zero term to be positive. if( a<0 || (a==0 && b<0) || (a==0 && b==0 && c<0) ) { a = -a; b = -b; c = -c; } // With those two normalizations, the representation // of a line should be unique. this.a = a; this.b = b; this.c = c; } /** * Create a pretty String for debugging * * @return A Pretty String */ public String toString() { return "[" + a + "," + b + "," + c + "]"; } @Override /** * Compare another Line to this one. * * @param l Another line * @return The usual for compareTo */ public int compareTo( Line l ) { int diff = a - l.a; if( diff==0 ) diff = b - l.b; if( diff==0 ) diff = c - l.c; return diff; } } /** * Driver. * @throws Exception */ public void doit() throws Exception { sc = new Scanner( System.in ); ps = System.out; int n = sc.nextInt(); // We'll need Triangle Numbers a little later. // Actually, these are reverse Triangle numbers. // So, x is the triangle Number of triangle[x]. int triangle[] = new int[n*(n+1)/2+1]; Arrays.fill( triangle, 0 ); int tri = 0; for( int i=1; i<=n; i++ ) { tri += i; triangle[tri] = i; } // Read in the spots Point spots[] = new Point[n]; for( int i=0; i= 0 ) ++count; if( count>max ) max=count; // Start a new batch count = 2; } lastpoint = thispoint; } // We'll pull the same trick with the midlines. count = 2; Line lastline = midlines[0]; for( int i=1; imax ) max=count; count = 2; } lastline = thisline; } // For Lines that go through Spots, we'll use a different trick. // First, we'll count the number of Lines that are the same. count = 1; lastline = lines[0]; for( int i=1; imax ) max=count; count = 1; } lastline = thisline; } } // And finally, the number we have to match is n minus // the max already matched. ps.println( n - max ); //System.exit(0); } /** * @param args */ public static void main( String[] args ) throws Exception { new symmetry_vanb().doit(); } }