/* Queen Collison, MCPC 2010 Problem D by Andy Harrington input: Each dataset: n g, where n indicates an n x n board size, and g is the number linear patterns of queens g lines: k x0 y0 dx dy for k points at equal intervals */ import java.util.*; import java.io.*; import static java.lang.Math.*; import java.awt.Point; public class collision { static int n, g, nPt, tot,// board size, tot linear seq, # of queens, tot collisions k, x0, y0, dx, dy, x, y, // pattern line, current point MAX_N = 29999, MAX_G = 249; // check against final problem statement! public static void main(String[] args) throws Exception { String file = (args.length > 0) ? args[0] : "collision.in"; Scanner in = new Scanner(new File(file)); while (true) { n = in.nextInt(); if (n == 0) break; HashSet pts = new HashSet(); // for judge test boolean[] xVal = new boolean[n+1], yVal = new boolean[n+1], sum = new boolean[2*n+2], dif = new boolean[2*n]; // dif offset by n tot = nPt = 0; g = in.nextInt(); for (int i = 0; i < g; i++) { k = in.nextInt(); x = x0 = in.nextInt(); y = y0 = in.nextInt(); dx = in.nextInt(); dy = in.nextInt(); nPt += k; for (int j=0; j < k; j++) { test(x, y, pts); // judge tests set (xVal, x); set (yVal, y); set(sum, x+y); set(dif, x-y+n); x += dx; y += dy; } } System.out.println(tot); judgeCheck(); } } static void set(boolean[] a, int i) { if (a[i]) tot++; else a[i] = true; } // only judge's tests follow: static void test(int x, int y, HashSet pts) { if (x <= 0 || x > n || y <= 0 || y > n) System.out.format("Out of range!! %s, %s in %s %s %s %s %s%n", x, y, k,x0,y0,dx,dy); Point xy = new Point(x, y); if (pts.contains(xy)) System.out.format("Dup!! %s, %s in %s %s %s %s %s%n", x, y, k,x0,y0,dx,dy); else pts.add(xy); } static void judgeCheck() { // check against final problem statement (also MAX's at top)! if (n > MAX_N || g > MAX_G || nPt > n) System.err.println("Bad param!"); } }