import java.io.BufferedReader; import java.io.FileReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.ArrayList; import java.util.HashMap; import java.util.HashSet; import java.util.Set; /** * */ /** * @author zeil * */ public class FindPoly_zeil { public class Point extends java.awt.Point { public Point (int x, int y) { super(x,y); } public String toString() { return "(" + x + "," + y + ")"; } public boolean comesBefore (Point p) { return x < p.x || (x == p.x && y < p.y); } } // A graph mapping each point to the line segments adjacent to it. // This will be stored as a directed graph, so for each // line segment of type T running between p1 and p2, graph.get(p1) // will contain a LineSegment(p1,p2) and house.get(p2) will contain // a LineSegment(p2,p1). HashMap> graph; ArrayList rooms; static int lineSegmentCounter = 0; public class LineSegment { public Point p1; public Point p2; char wallType; int id; public LineSegment (Point p1, Point p2, char wtype) { this.p1 = p1; this.p2 = p2; wallType = wtype; if (wallType != 'W') { ++lineSegmentCounter; id = lineSegmentCounter; } else id = 0; } LineSegment normalize() { if (p1.comesBefore(p2)) { return this; } else { return flip(); } } LineSegment flip() { return new LineSegment(p2, p1, wallType); } public String toString() {return "" + id + " [" + p1.toString() + "," + p2.toString() + "]" + wallType;} @Override public int hashCode() { return p1.x + 13 * p1.y + 23 * p2.x + 17 * p2.y; } public boolean equals (Object obj) { LineSegment w = (LineSegment)obj; return w.wallType == wallType && w.p1.equals(p1) && w.p2.equals(p2); } } public class Path extends ArrayList { public boolean equals(Object obj) { Path p = (Path)obj; if (p.size() != size()) return false; for (int i = 0; i < size(); ++i) if (!get(i).equals(p.get(i))) return false; return true; } } class Room { public Path perimeter; public double area; public ArrayList connectors; public int roomNumber; public Room (Path p) { perimeter = p; long sum = 0L; connectors = new ArrayList(); for (int i = 1; i < perimeter.size(); ++i) { Point p0 = perimeter.get(i-1); Point p1 = perimeter.get(i); sum += (long)p0.y * (long)p1.x - (long)p1.y*(long)p0.x; for (LineSegment w: graph.get(p0)) { if (w.p2.equals(p1)) { if (w.wallType != 'W') connectors.add(w); break; } } } area = Math.abs(((double)sum)/2.0); } } static boolean DEBUG = false; public FindPoly_zeil() { graph = new HashMap>(); } public class Vertex { String id; Vertex figure; int figureSize; ArrayList adjacent; int nextAdj; boolean covered; Vertex (String ident) { id = ident; figure = this; figureSize = 0; adjacent = new ArrayList<>(); nextAdj = 0; covered = false; } Vertex find() { Vertex signature = figure; while (signature != signature.figure) { signature = signature.figure; } figure = signature; return signature; } void union (Vertex w) { Vertex sigv = find(); Vertex sigw = w.find(); sigw.figure = sigv; } public boolean equals( Object ov) { Vertex v = (Vertex)ov; return v.id.equals(id); } public int hashCode() { return id.hashCode(); } public String toString() { return id + ":(" + figure.id + ")"; } } HashMap vertexNames; ArrayList vertices; final void solve (BufferedReader bin) throws IOException { vertices = new ArrayList<>(); vertexNames = new HashMap<>(); String line = bin.readLine(); while (line != null) { String[] segmentParts = line.split(";"); for (String segmentStr: segmentParts) { if (segmentStr.length() > 0) { int k = segmentStr.indexOf("),("); String name1 = segmentStr.substring(0, k+1); String name2 = segmentStr.substring(k+2); Integer k1 = vertexNames.get(name1); if (k1 == null) { vertexNames.put(name1, vertices.size()); k1 = vertices.size(); vertices.add(new Vertex(name1)); } Integer k2 = vertexNames.get(name2); if (k2 == null) { vertexNames.put(name2, vertices.size()); k2 = vertices.size(); vertices.add(new Vertex(name2)); } Vertex v1 = vertices.get(k1); Vertex v2 = vertices.get(k2); v1.adjacent.add(v2); v2.adjacent.add(v1); } } line = bin.readLine(); } int nf = countFigures(); int np = countPolygons(); System.out.println("" + nf + " " + np); } private int countPolygons() { int nPoly = 0; for (Vertex v0: vertices) { if (v0.figure == v0 && v0.figureSize >= 3) { Vertex[] path = new Vertex[v0.figureSize+1]; path[0] = v0; int k = 0; v0.nextAdj = 0; v0.covered = true; while (k >= 0 && k <= v0.figureSize) { Vertex v = path[k]; if (k == v0.figureSize) { if (v == v0) { break; } else { v.covered = false; path[k] = null; --k; if (k < 0) break; } } else if (v.nextAdj < v.adjacent.size()) { Vertex w = v.adjacent.get(v.nextAdj); if (w == v0 && k == v0.figureSize-1) { break; } else if (! w.covered) { ++v.nextAdj; ++k; path[k] = w; w.covered = true; w.nextAdj = 0; } else { ++v.nextAdj; } } else { v.covered = false; path[k] = null; --k; if (k < 0) break; } } if (k > 0) { ++nPoly; } } } return nPoly; } private int countFigures() { for (Vertex v: vertices) { for (Vertex w: v.adjacent) { v.union(w); } } int nFigures = 0; for (Vertex v: vertices) { if (v.figure == v) { ++nFigures; } Vertex fig = v.find(); fig.figureSize += v.adjacent.size(); } for (Vertex v: vertices) { if (v.figure == v) { v.figureSize /= 2; //System.err.println("Figure " + v + " is size " + v.figureSize); } } return nFigures; } /** * @param args * @throws IOException */ public static void main (String[] argv) throws IOException { BufferedReader in; if (argv.length > 0) { in = new BufferedReader(new FileReader(argv[0])); } else { in = new BufferedReader (new InputStreamReader(System.in)); } new FindPoly_zeil().solve (in); } }