// Solution to "I Conduit" by Bob Roos // First, order each point pair in increasing order of x-coordinates // (for vertical, order by y-coordinates). This guarantees that // parallel line segments (thought of as vectors) have the same "direction". // // Next, sort the segments into groups where all segments in a group lie along // the same infinite line (match slopes and one point; the point may be // on an extension of the line segment). // // In each group, sort segments by x-coordinates of the starting point (for // vertical lines, sort by y-coordinates of starting point). // // Finally, scan each sorted group looking for "gaps" in the x-values of // the endpoints (or y-values in the case of vertical lines). We are // essentially projecting the line segments onto one of the axes and // looking for breaks. import java.util.*; import java.io.*; class Segment { public double x1,y1,x2,y2; // segment endpoints public int id; // group number public double run, rise; // delta x and delta y, normalized so that // the larger in magnitude of the two is 1.0. // Constructor: Segment(double x1,double y1,double x2,double y2,int id) { this.x1 = x1; this.y1 = y1; this.x2 = x2; this.y2 = y2; this.id = id; run = 0.0; rise = 0.0; } } public class Conduits { static BufferedReader in; static StringTokenizer tok; static int n; // number of line segments static double x1[], y1[], x2[], y2[]; // the segment endpoints static Vector seg; // segments in final drawing static int maxId; // number of distinct line groups public static void main(String[] args) throws IOException { in = new BufferedReader(new InputStreamReader(System.in)); String line = in.readLine().trim(); // Main input/process/output loop: while (line != null) { n = Integer.parseInt(line); if (n == 0) break; x1 = new double[n]; y1 = new double[n]; x2 = new double[n]; y2 = new double[n]; for (int i = 0; i < n; i++) { line = in.readLine().trim(); tok = new StringTokenizer(line); x1[i] = Double.parseDouble(tok.nextToken()); y1[i] = Double.parseDouble(tok.nextToken()); x2[i] = Double.parseDouble(tok.nextToken()); y2[i] = Double.parseDouble(tok.nextToken()); // Orient all line segments by x-coordinate (or // by y-coordinate if x's are equal) if (Math.abs(x1[i]-x2[i]) >= .00000001) { if (x1[i] > x2[i]) { double swap = x1[i]; x1[i] = x2[i]; x2[i] = swap; swap = y1[i]; y1[i] = y2[i]; y2[i] = swap; } } else if (y1[i] > y2[i]) { double swap = x1[i]; x1[i] = x2[i]; x2[i] = swap; swap = y1[i]; y1[i] = y2[i]; y2[i] = swap; } } System.out.println(process()); line = in.readLine().trim(); } } ////////////////////////////////////////////////////////// // All the work for each problem instance gets done here. public static int process() { // Line segments sorted by group go into vector "seg": seg = new Vector(); maxId = 0; // number of groups found so far for (int i = 0; i < n; i++) { // Insert the i-th input segment into the seg vector by // group identifier: int j = 0; int id = maxId+1; while (j < seg.size()) { // See if segment i belongs to the same group as the j-th // segment already stored in the vector: if (sameLine(i,j)) { //System.out.println("Lines " +i+" and " +j+" are the same."); id = ((Segment)seg.get(j)).id; break; } //else //System.out.println("Lines " +i+" and " +j+" are different."); j++; } insertSeg(i,j+1,id); maxId = Math.max(maxId,id); } // mergeSeg sorts each group by x-coordinate and does the final // scan of the groups: return mergeSeg(); } ////////////////////////////////////////////////////////// // Returns "true" if i-th input segment aligns with j-th vector element public static boolean sameLine(int i, int j) { // We identify lines with their "normalized" run and rise values; i.e., // we take the values of (delta x)/k and (delta y)/k, where k is the // value in {delta x, delta y} having the larger magnitude. double dxi = x2[i]-x1[i]; double dyi = y2[i]-y1[i]; Segment s = (Segment) seg.get(j); double dxj = s.x2-s.x1; double dyj = s.y2-s.y1; double run, rise; if (Math.abs(dxi) > Math.abs(dyi)) { run = 1.0; rise = dyi/dxi; } else { rise = 1.0; run = dxi/dyi; } // next four lines inserted by JPB if (run < 0) { run *= -1; rise *= -1; } if (Math.abs(run-s.run) >= .00000001 || Math.abs(rise-s.rise) >= .00000001) return false; // see if both points of i-th line lie on the j-th segment: dxi = x1[i]-s.x1; dyi = y1[i]-s.y1; if (eq(x1[i],s.x1) && eq(y1[i],s.y1)) { dxi = x1[i]-s.x2; dyi = y1[i]-s.y2; } if (Math.abs(dxi) - Math.abs(dyi) >= 0.00000001 && Math.abs(dxi) > 0.00000001) { run = 1.0; rise = dyi/dxi; } else { rise = 1.0; run = dxi/dyi; } // next four lines inserted by JPB if (run < 0) { run *= -1; rise *= -1; } if (Math.abs(run-s.run) >= .00000001 || Math.abs(rise-s.rise) >= .00000001){ //System.out.println("x1 not on segment "+j+": run, s.run = "+run+" "+s.run //+", rise, s.rise =" + rise + " "+s.rise); return false; } dxi = x2[i]-s.x1; dyi = y2[i]-s.y1; if (eq(x2[i],s.x1) && eq(y2[i],s.y1)) { dxi = x2[i]-s.x2; dyi = y2[i]-s.y2; } if (Math.abs(dxi) - Math.abs(dyi) >= 0.00000001 && Math.abs(dxi) > 0.00000001) { run = 1.0; rise = dyi/dxi; } else { rise = 1.0; run = dxi/dyi; } // next four lines inserted by JPB if (run < 0) { run *= -1; rise *= -1; } if (Math.abs(run-s.run) >= .00000001 || Math.abs(rise-s.rise) >= .00000001){ //System.out.println("x2 not on segment "+j+": run, s.run = "+run+" "+s.run //+", rise, s.rise =" + rise + " "+s.rise); return false; } return true; } ////////////////////////////////////////////////////////// // Insert a segment into the "seg" vector according to group // (i.e., group all line segments that lie along the same infinite line): public static void insertSeg(int i, int j, int id) { Segment temp = new Segment(x1[i],y1[i],x2[i],y2[i],id); double dxi = x2[i]-x1[i]; double dyi = y2[i]-y1[i]; if (Math.abs(dxi) > Math.abs(dyi)) { temp.run = 1.0; temp.rise = dyi/dxi; } else { temp.rise = 1.0; temp.run = dxi/dyi; } // next four lines inserted by JPB if (temp.run < 0) { temp.run *= -1; temp.rise *= -1; } if (j < seg.size()) seg.insertElementAt(temp,j); else seg.add(temp); //System.out.println("Inserting ("+temp.x1+","+temp.y1+"), (" // +temp.x2+","+temp.y2+") "+temp.id // +"; run = " + temp.run + ", rise = " + temp.rise); } ////////////////////////////////////////////////////////// public static int mergeSeg() { int i = 0; // Sort segments within each group while (i < seg.size()) { int currentId = ((Segment)seg.get(i)).id; int start = i; i++; // Insertion sort on starting x-coordinate int j = i; while (j < seg.size() && ((Segment)seg.get(j)).id == currentId) { Segment s = (Segment)seg.get(j); double x = s.x1; int k = j-1; // The next two lines are added by JPB and replace the commented line after them double y = s.y1; while (k >= start && (x < ((Segment)seg.get(k)).x1 || (x == ((Segment)seg.get(k)).x1 && y < ((Segment)seg.get(k)).y1))) { // while (k >= start && x < ((Segment)seg.get(k)).x1) { seg.setElementAt(seg.get(k),k+1); k--; } seg.setElementAt(s,k+1); j++; } i = j; } //System.out.println("Segment list:"); //for (int j = 0; j < seg.size(); j++) { // Segment s = (Segment)seg.get(j); // System.out.println(" ("+s.x1+","+s.y1+"), ("+s.x2+","+s.y2+") "+s.id // +"; run = " + s.run + ", rise = " + s.rise); //} // Now run through the sorted lists and find number of disjoint // segments in each group: i = 0; int count = 0; while (i < seg.size()) { count++; Segment s = (Segment)seg.get(i); int currentId = s.id; int sortStyle = 0; double extent = s.x2; if (Math.abs(s.run) < .00000001) { sortStyle = 1; extent = s.y2; } int j = i+1; while (j < seg.size() && ((Segment)seg.get(j)).id == currentId) { Segment t = (Segment)seg.get(j); switch (sortStyle) { case 0: if (t.x1 > extent) { count++; extent = t.x2; } else { extent = Math.max(extent,t.x2); } break; case 1: if (t.y1 > extent) { count++; extent = t.y2; } else { extent = Math.max(extent,t.y2); } } j++; } i = j; } return count; } public static boolean eq(double a, double b) { return (Math.abs(a-b) < 0.00000001); } }