import java.io.*; import java.util.*; import java.awt.geom.*; /** * Solution to Funhouse * * @author vanb */ public class funhouse { public Scanner sc; public PrintStream ps; // Bigger than the biggest possible room public static final int MAX = 2*1001*1001+1; /** * A node of a max flow graph. * * @author vanb */ public class Node { // Has the node been visited? public boolean visited = false; // List of edges from this node public LinkedList edges = new LinkedList(); // If this node has been visited, what edge did we get here from? public Edge from = null; /** * Clear this node for a new graph */ public void clear() { visited = false; edges.clear(); from = null; } } /** * An edge of a max flow graph. * * @author vanb */ public class Edge { Node destination; int capacity; Edge dual; public Edge( Node d, int c ) { capacity = c; destination = d; dual = null; } } /** * Create a link between two nodes of a max flow graph. * * @param n1 From node * @param n2 To node * @param cost Cost to go from n1 to n2 */ public void link( Node n1, Node n2, int cost ) { Edge e12 = new Edge( n2, cost ); Edge e21 = new Edge( n1, 0 ); e12.dual = e21; e21.dual = e12; n1.edges.add( e12 ); n2.edges.add( e21 ); } /** Queue for the Ford/Fulkerson algorithm */ public LinkedList queue = new LinkedList(); /** * Perform the Ford/Fulkerson algorithm on a graph. * * @param src Source node * @param snk Sink node * @param nodes The graph, represented as a list of nodes * @return The max flow from the source to the sink */ public int fordfulkerson( Node src, Node snk, List nodes ) { int total = 0; // Keep going until you can't get from the source to the sink for(;;) { // Reset the graph for( Node node : nodes ) { node.visited = false; node.from = null; } // Reset the queue // Start at the source queue.clear(); queue.add( src ); src.visited = true; // Have we found the sink? boolean found = false; // Use a breadth-first search to find a path from the source to the sink while( queue.size()>0 ) { Node node = queue.poll(); // Have we found the sink? If so, break out of the BFS. if( node==snk ) { found = true; break; } // Look for edges to traverse for( Edge edge : node.edges ) { Node dest = edge.destination; // If this destination hasn't been visited, // and the edge has capacity, // put it on the queue. if( edge.capacity>0 && !dest.visited ) { // Node has been visited dest.visited = true; // Remember the edge that got us here dest.from = edge; // Add to the queue queue.add( dest ); } } } // If we were unable to get to the sink, then we're done if( !found ) break; // Otherwise, look along the path to find the minimum capacity int min = Integer.MAX_VALUE; for( Node node = snk; node.from != null; ) { Edge edge = node.from; if( edge.capacity < min ) min = edge.capacity; node = edge.dual.destination; } // Add that minimum capacity to the total total += min; // Go back along the path, and for each edge, move the min // capacity from the edge to its dual. for( Node node = snk; node.from != null; ) { Edge edge = node.from; edge.capacity -= min; edge.dual.capacity += min; node = edge.dual.destination; } } // Return the total return total; } /** * A wall connected to a point. * This object keeps track of both the wall, * and the angle of the wall from this point. */ public class WallAngle implements Comparable { public Wall wall; public double angle; public WallAngle( Point point, Wall wall ) { this.wall = wall; angle = point==wall.points[0] ? Math.atan2( wall.points[1].y-point.y, wall.points[1].x-point.x ) : Math.atan2( wall.points[0].y-point.y, wall.points[0].x-point.x ); } public int compareTo( WallAngle p ) { return Double.compare( angle, p.angle ); } } /** * A point. This object keeps track of the (x,y) coords of the point, * and all walls that have this point as an endpoint. */ public class Point { public int x, y; public LinkedList walls = new LinkedList(); /** * Create a Point. * @param x X coord * @param y Y coord */ public Point( int x, int y ) { this.x = x; this.y = y; } /** * Add a wall that has this point as an endpoint. * @param wall Wall to add. */ public void addEdge( Wall wall ) { walls.add( new WallAngle( this, wall ) ); } /** * Look for the next wall in sequence * * @param wall This wall * @return The next wall */ public Wall nextWall( Wall wall ) { Wall next = null; // Go through the list, looking for this wall. for( WallAngle pw : walls ) { if( pw.wall == wall ) break; next = pw.wall; } // The only way next can be null // is if this wall is the first wall in the list, // in which case, the next wall is the last one in the list. if( next==null ) { next = walls.getLast().wall; } return next; } } /** * A Wall between two points */ public class Wall { public int index; public Point points[] = new Point[2]; public char door; public Room rooms[] = new Room[2]; /** * If we know one endpoint, return the other * @param p One endpoint * @return The other endpoint */ public Point other( Point p ) { return p==points[0] ? points[1] : points[0]; } } /** * A room, which is a polygon */ public class Room { public LinkedList walls = null; public LinkedList neighbors = new LinkedList(); public int area = 0; public int index = 0; public boolean hasEntrance = false; public boolean hasExit = false; /** * Compute the area of this room, and figure out if * it has an entrance or an exit. */ public void computeAreaAndEntranceExit() { area = 0; // Find the point that's shared between // the first and last wall Wall f = walls.getFirst(); Wall l = walls.getLast(); Point last = null; for( int i=0; i<2; i++ )for( int j=0; j<2; j++ ) { if( f.points[i]==l.points[j] ) { last = f.points[i]; } } for( Wall wall : walls ) { // Mark this room if it has a entrance or an exit if( wall.door=='E' ) hasEntrance = true; if( wall.door=='X' ) hasExit = true; Point other = wall.other( last ); area += (other.y+last.y)*(other.x-last.x); last = other; //System.err.println( "(" + wall.points[0].x + "," + wall.points[0].y + ")-(" + wall.points[1].x + "," + wall.points[1].y + ")" ); } area = Math.abs( area ); //System.err.println( "Area of room is " + area); } } public HashMap points = new HashMap(); /** * Add a point. create a new Point structure if needed, OR return one that already exists. * * @param x X coordinate * @param y Y coordinate * @return Point object for this (x,y) point */ public Point addPoint( int x, int y ) { String key = "" + x + "," + y; Point point = points.get( key ); if( point==null ) { point = new Point(x,y); points.put( key, point ); } return point; } public HashMap rooms = new HashMap(); /** * Build a room, look for it in the hash table. * * @param wall A starting wall * @param p1 A point of the wall - it's the direction we're moving around the room * @return A new room */ public Room buildRoom( Wall wall, Point p1 ) { LinkedList poly = new LinkedList(); // Build up a polygon, starting with this wall poly.add( wall ); Point p = p1; Point p0 = wall.other( p ); while( p!=p0 ) { wall = p.nextWall( wall ); p = wall.other( p ); poly.add( wall ); } Room room = new Room(); room.walls = poly; room.computeAreaAndEntranceExit(); return room; } /** * Add a room to our list of rooms IF it isn't there already. * * @param room A room * @return The room, or the original if it's already in our list */ public Room addRoom( Room room ) { // Create a unique key for this room. // No two rooms will have exactly the same set of walls. // So, we'll snag the wall indices, sort them, // and make a String out of them. int indices[] = new int[room.walls.size()]; int i=0; for( Wall wall : room.walls ) { indices[i++] = wall.index; } Arrays.sort( indices ); String key = Arrays.toString( indices ); // Look to see if there's another room // with the same key Room otherroom = rooms.get( key ); if( otherroom==null ) { // If not, then this is a new room. // Add it. room.index = rooms.size(); rooms.put( key, room ); } else { // If this room is a duplicate, // then we'll discard it and // return the original. room = otherroom; } return room; } /** * Driver. * @throws Exception */ public void doit(String file) throws Exception { sc = new Scanner( new File( file ) ); ps = System.out; //new PrintStream( new FileOutputStream( "funhouse.solution" ) ); // Set up some data structures beforehand. // We'll just need to clear them each time through, // rather than reallocating them. LinkedList walls = new LinkedList(); LinkedList nodes = new LinkedList(); Node source = new Node(); Node sink = new Node(); Node enter[] = new Node[1000]; Node exit[] = new Node[1000]; boolean linked[][] = new boolean[1000][1000]; for( int i=0; i<1000; i++ ) { enter[i] = new Node(); exit[i] = new Node(); } for(;;) { int n = sc.nextInt(); if( n==0 ) break; // Input the walls walls.clear(); points.clear(); rooms.clear(); for( int i=0; i