import java.util.Collections; import java.util.Scanner; import java.util.ArrayList; public class ISoar { Scanner in = new Scanner(System.in); ArrayList buildings; void start() { while (true) { float L = in.nextFloat(); // End-of-input condition if (L <= 0) return; // Input test case buildings = new ArrayList(); while (true) { float x1 = in.nextFloat(); float x2 = in.nextFloat(); // Account for buildings outside of highway window if (x1 < 0) x1 = 0f; if (x2 > L) x2 = L; // End-of-test case condition if (x1 > x2) break; buildings.add(new Building(x1, x2)); } // Sort buildings by increasing left endpoint Collections.sort(buildings); // Merge redundant intervals merge(); // Calculate uncovered distance for (int i = 0; i < buildings.size(); i++) { L -= buildings.get(i).getDX(); } // Print desired output System.out.printf("The total planting length is %.1f\n", L); } } void merge() { // List with only validated intervals ArrayList mergedList = new ArrayList(); // Initialize intervals to consider float left = buildings.get(0).xL; float right = buildings.get(0).xR; for (int i = 1; i < buildings.size(); i++) { float cur_left = buildings.get(i).xL; float cur_right = buildings.get(i).xR; // Ignore intervals completely inside left-right interval if (cur_left > left && cur_right < right) continue; // Merge redundant intervals if necessary if (cur_left <= right && cur_right > right) { right = cur_right; } // Otherwise, add verified interval to merged list else { mergedList.add(new Building(left, right)); left = cur_left; right = cur_right; } } // Have to add last interval considered mergedList.add(new Building(left, right)); // Replace original list with merged list buildings = mergedList; } // Class for each building class Building implements Comparable { // Left endpoint float xL; // Right endpoint float xR; // Constructor Building(float a, float b) { xL = a; xR = b; } // Length of building float getDX() { return this.xR - this.xL; } // For sorting (will sort by increasing xL) public int compareTo(Building other) { float starts = this.xL - other.xL; if (starts > 0f) return 1; else if (starts < 0f) return -1; else return 0; } // For debugging public String toString() { return xL + " - " + xR; } } public static void main(String[] args) { new ISoar().start(); } }