import java.util.*; public class Target { public final static int MAX=1000; public static Point [] b = new Point[MAX]; // balloon locations public static Line [] lines = new Line[MAX/3]; public static int nlines; public static int minLines; // minimum number of lines used (set in bestCover) public static boolean onLine(Point p, Line l) { int dx = p.x-l.start.x; int dy = p.y-l.start.y; //cout << " dx, dy = " << dx << ',' << dy << endl; //cout << " delx, dely = " << l.delx << ',' << l.dely << endl; if (dx*l.dely != dy*l.delx) return false; int dz = p.z-l.start.z; if (dz*l.dely != dy*l.delz) return false; //cout << " dx, dz = " << dx << ',' << dz << endl; //cout << " delx, delz = " << l.delx << ',' << l.delz << endl; return (dx*l.delz == dz*l.delx); } public static void getLines(int n) // determine lines which pass through 3 or more balloons { int i, j, k; int [] list = new int[MAX]; int count; nlines = 0; for(i=0; i=0; k--) { if (lines[k+1].n < lines[k].n) break; Line temp = lines[k+1]; lines[k+1] = lines[k]; lines[k] = temp; } //cout << endl; nlines++; } } } } public static void bestCover(int i, int numL, int numB, int hits[], int cover, int linesUsed) { //cout << "i, cover, linesUsed" << i << ',' << cover << ',' << linesUsed << endl; int j; if (i == numL || numB-cover <=2) { if (linesUsed + (numB-cover+1)/2 < minLines) { minLines = linesUsed + (numB-cover+1)/2; } } else if (linesUsed + (numB-cover)/lines[i].n >= minLines) return; else { // use line i; int newHits=0; for(j=0; j=3) public int [] list; // list of balloons }