import java.util.*; public class Apoly3 { public static final int MAXD = 10000; // max value for |x|, |y| public static final int MAXPOLYGONS = 100; public static final int MAXSEGS = 20; public static final double PI = 4*Math.atan(1.0); public static TreeSet xxvals = new TreeSet(); // scan line positions public static boolean equals(double a, double b) { return (Math.abs(a-b) < 0.000001); } public static polygon [] polygons = new polygon[MAXPOLYGONS]; public static int nPoly; public static boolean lineIntersect(double x1, double y1, double x2, double y2, double x3, double y3, double x4, double y4, point pint) { double dx1 = x2-x1; double dx2 = x4-x3; double dy1 = y2-y1; double dy2 = y4-y3; double denom = dy2*dx1-dy1*dx2; if (equals(denom, 0.0)) { return false; // colinear lines handled already } double dx3 = x1-x3; double dy3 = y1-y3; double t = (dx2*dy3-dy2*dx3)/denom; double u = (dx1*dy3-dy1*dx3)/denom; if (equals(t, 0.0) || t < 0.0) return false; if (equals(t, 1.0) || t > 1.0) return false; if (equals(u, 0.0) || u < 0.0) return false; if (equals(u, 1.0) || u > 1.0) return false; pint.x = x1 + t*dx1; pint.y = y1 + t*dy1; return true; } public static void checkForIntersection(segment s1, polygon poly) { double xint, yint; for(int i=0; i polygons[i].xmax) polygons[i].xmax = p2.x; if (p2.y < polygons[i].ymin) polygons[i].ymin = p2.y; if (p2.y > polygons[i].ymax) polygons[i].ymax = p2.y; s.p2 = new point(p2); polygons[i].add(s); s.p1 = s.p2; } p2.x = x; p2.y = y; xxvals.add(p2.x); s.p2 = new point(p2); polygons[i].add(s); paintArea += polygons[i].getArea(); for(int j=0; j polygons[k].xmax)) continue; double ymin = seg.p1.y, ymax = seg.p2.y; if (ymax < ymin) { double tmp = ymax; ymax = ymin; ymin = tmp; } if ((!equals(ymax, polygons[k].ymin) && ymax < polygons[k].ymin) || (!equals(ymin, polygons[k].ymax) && ymin > polygons[k].ymax)) continue; checkForIntersection(seg, polygons[k]); } } } scanLine sLine = new scanLine(nPoly, polygons); double totalArea = 0.0; Iterator it = xxvals.iterator(); double nextx=(double)it.next(); do { double x = nextx; sLine.buildScanLine(x); while (it.hasNext()) { nextx = (double)it.next(); if (!equals(x, nextx)) break; } if (equals(x,nextx)) break; totalArea += sLine.getArea(nextx); } while(true); System.out.printf("%.6f %.6f\n", paintArea, totalArea); } } class point { public double x, y; public point() { x = 0.0; y = 0.0; } public point(double xx, double yy) { x = xx; y = yy; } public point(point otherp) { x = otherp.x; y = otherp.y; } public boolean equals(point rhs) { return (Apoly3.equals(x, rhs.x) && Apoly3.equals(y, rhs.y)); } } class segment { public point p1, p2; double ang; // angle from point with lowest x to point with highest x segment() { p1 = new point(); p2 = new point(); } segment(point pp1, point pp2) { p1 = new point(pp1.x, pp1.y); p2 = new point(pp1.x, pp2.y); } void order() { if ((!Apoly3.equals(p2.x, p1.x) && p2.x < p1.x) || (Apoly3.equals(p2.x, p1.x) && p2.y < p1.y)) { point tmp = p1; p1 = p2; p2 = tmp; } ang = Math.atan2(p2.y-p1.y, p2.x-p1.x); } } class polygon { public Vector segs = new Vector(); public int nsegs; public double xmin, xmax, ymin, ymax; public double area; public polygon() { nsegs = 0; } public void add(segment s) { area += (s.p2.x - s.p1.x)*(s.p2.y+s.p1.y); segment s2 = new segment(); s2.ang = s.ang; s2.p1.x = s.p1.x; s2.p1.y = s.p1.y; s2.p2.x = s.p2.x; s2.p2.y = s.p2.y; s2.order(); segs.add(s2); nsegs++; } public double getArea() { return area/2.0; } } class scanLineNode { public double x, y; public int ipoly, iseg; // else it's an intersecting segment public scanLineNode() { x = 0.0; y = 0.0; ipoly = -1; iseg = -1; } public scanLineNode(double xx, double yy, int ip1, int is1) { x = xx; y = yy; ipoly = ip1; iseg = is1; } boolean lessThan(scanLineNode rhs) { return x > rhs.x; } } class scanLine { public int n; // number of polygons public int size; // number of nodes on scan line public scanLineNode [] nodes; // the scan line public double prevXHigh; // used by getArea public polygon [] polygons; public scanLine(int nn, polygon [] p) { n = nn; polygons = p; size = 0; nodes = new scanLineNode[2*Apoly3.MAXSEGS*n]; for(int i=0; i<2*n; i++) nodes[i] = new scanLineNode(); prevXHigh = -2*Apoly3.MAXD; } public double getYval(segment s, double x) { point p1 = s.p1; point p2 = s.p2; if (Apoly3.equals(p2.x, p1.x)) return p2.y; return p1.y + (p2.y-p1.y)/(p2.x - p1.x)*(x - p1.x); } public void insert(scanLineNode node) { //System.out.println("in insert, inserting " + node.x + "," + node.y); int i=size; while (i > 0 && !Apoly3.equals(nodes[i-1].y, node.y) && nodes[i-1].y > node.y) { nodes[i] = nodes[i-1]; i--; } segment s = (segment)polygons[node.ipoly].segs.elementAt(node.iseg); while(i > 0 && Apoly3.equals(nodes[i-1].y, node.y) && ((segment)(polygons[nodes[i-1].ipoly].segs.elementAt(nodes[i-1].iseg))).ang > s.ang) { nodes[i] = nodes[i-1]; i--; } nodes[i] = node; size++; } public double getArea(double xhigh) { if (Apoly3.equals(xhigh, prevXHigh)) return 0.0; double area = 0.0; boolean [] present = new boolean[n]; double xlow = nodes[0].x; double ylow1 = 2*Apoly3.MAXD; // artificially high double ylow2 = 2*Apoly3.MAXD; double yhigh1 = -2*Apoly3.MAXD; // artificially low double yhigh2 = -2*Apoly3.MAXD; int count = 0; // number of polygons in current // vertical section of scan line for(int i=0; i yhigh1) { yhigh1 = nd.y; double y = getYval((segment)polygons[nd.ipoly].segs.elementAt(nd.iseg), xhigh); if (y > yhigh2) yhigh2 = y; } } //System.out.println("here"); if (count == 0) { //System.out.println(xlow + "--" + xhigh + ", " + ylow1 + "--" + yhigh1 + ", " + ylow2 + "--" + yhigh2); area += (xhigh-xlow)*(yhigh1-ylow1+yhigh2-ylow2)/2.0; ylow1 = ylow2 = 2*Apoly3.MAXD; yhigh1 = yhigh2 = -2*Apoly3.MAXD; } } return area; } public void buildScanLine(double x) { //System.out.println("scanline x = " + x); size = 0; for(int i=0; i polygons[i].xmax) continue; for(int j=0; j