/** * CTU Open 2019 * Problem Solution: Screamers * Idea: Keep track of the nearest eligible boundary segment. * Time: O(n^3), where n is the number of boundary segments. */ import java.util.*; import java.io.*; import java.math.*; import java.text.DecimalFormat; public class screamers { static final DecimalFormat OUTFORM = new DecimalFormat("0.000000000000"); static final double EPS = 1E-9; enum EventType { START, END, CROSS } public class Point { public Point(double x_, double y_, double h_) { x=x_; y=y_; h=h_; } public Point(double x_, double y_) { x=x_; y=y_; h=0; } public Point(Point p) { x=p.x; y=p.y; h=p.h; segids=new int[p.segids.length]; for(int i=0; i= low().y && c.y <= high().y && Math.abs(c.x-p.x) < EPS); } // Not on the segment's line. if(Math.abs(c.y - co[0]*c.x - co[1]) > EPS) return false; return (c.x >= left().x && c.x <= right().x); } // Assumes the segment is axis-parallel and oriented from p to q. // E.g. if goes up, then distance on the left is positive. double ortho_dst(Point o) { if(p.x==q.x) { return (q.y>p.y ? p.x-o.x : o.x-p.x); } else { assert p.y==q.y; return (q.x q.y ? p : q); } Point left() { return new Point(p.x < q.x ? p : q); } Point right() { return new Point(p.x > q.x ? p : q); } void print() { System.out.printf("%d: (%f, %f) -> (%f, %f)\n", id, p.x, p.y, q.x, q.y); } Point p, q; int id=-1; } class Event { Event(Point p_, int seg_id, EventType t_) { p = new Point(p_); seg_ids.add(seg_id); t = t_; } Event(Point p_, int[] seg_ids_) { p = new Point(p_); for (int id : seg_ids_) seg_ids.add(id); t = EventType.CROSS; } Point p; // seg_ids are unused (would be useful for O(n^2) solution) ArrayList seg_ids = new ArrayList(); EventType t; } class Sortbyx implements Comparator { // Increasing x. If x equal, increasing y. public int compare(Event a, Event b) { if(a.p.x != b.p.x) return (int)Math.signum(a.p.x - b.p.x); return (int)Math.signum(a.p.y - b.p.y); } } // The point in the intersection, if it exists. // For overlapping segments, returns the two endpoints of the intersection. Point[] intersect (Segment k, Segment l) { return intersect(k,l,false); } // If kpqhalfline, k is a p->q halfline. Point[] intersect (Segment k, Segment l, boolean kpqhalfline) { double kc[] = k.coeffs(); double lc[] = l.coeffs(); boolean kvert = (kc.length == 0); boolean lvert = (lc.length == 0); Point klow = k.low(); Point khi = k.high(); Point llow = l.low(); Point lhi = l.high(); if(kvert) { if(kpqhalfline) { // Halfline going up -> extend up to lhi. if(k.p.y == klow.y && khi.y < lhi.y) khi.y = lhi.y; // Halfline going down -> extend up to llow. if(k.p.y == khi.y && klow.y > llow.y) klow.y = llow.y; } Segment kext = new Segment(klow, khi, k.id); // Both segments vertical if(lvert) { // Segments on different lines if(Math.abs(klow.x - llow.x) >= EPS) return new Point[0]; double x = klow.x; // Same line, but disjoint if(khi.y < llow.y || klow.y > lhi.y) return new Point[0]; // Overlapping return new Point[] { new Point(x, Math.max(klow.y, llow.y)), new Point(x, Math.min(khi.y, lhi.y)) }; } // Only k vertical. double x = klow.x; Point inter = new Point(x, lc[0] * x + lc[1]); if(kext.contains(inter) && l.contains(inter)) return new Point[] { inter }; else return new Point[0]; } Point kleft = k.left(); Point kright = k.right(); Point lleft = l.left(); Point lright = l.right(); if(kpqhalfline) { // Extend to the right. if(k.p.x == kleft.x && kright.x < lright.x) { double xdiff = lright.x - kright.x; kright.x += xdiff; kright.y += xdiff * kc[0]; } // Extend to the left. if(k.p.x == kright.x && kleft.x > lleft.x) { double xdiff = lleft.x - kleft.x; kleft.x += xdiff; kleft.y += xdiff * kc[0]; } } Segment kext = new Segment(kleft, kright, k.id); if(lvert) { double x = l.p.x; Point inter = new Point(x, kc[0] * x + kc[1]); if(kext.contains(inter) && l.contains(inter)) return new Point[] { inter }; else return new Point[0]; } // Parallel segments if(Math.abs(kc[0] - lc[0]) < EPS) { // Segments on different lines if(Math.abs(kc[1] - lc[1]) >= EPS) return new Point[0]; // Same line, but disjoint if(kright.x < lleft.x || kleft.x > lright.x) return new Point[0]; // Overlapping Point ileft = new Point(kleft.x > lleft.x ? kleft : lleft); Point iright = new Point(kright.x < lright.x ? kright : lright); return new Point[] { ileft, iright }; } double resx = (kc[1] - lc[1]) / (lc[0] - kc[0]); double resy = lc[0] * resx + lc[1]; Point inter = new Point(resx, resy); if(kext.contains(inter) && l.contains(inter)) return new Point[] { inter }; else return new Point[0]; } boolean wedge_contains (Segment bdry, Point c) { double diff = bdry.ortho_dst(c); if(diff < 0) return false; if(bdry.is_vertical()) { Point blow = bdry.low(); Point bhigh = bdry.high(); return (c.y <= bhigh.y + diff && c.y >= blow.y - diff); } else { Point bleft = bdry.left(); Point bright = bdry.right(); return (c.x <= bright.x + diff && c.x >= bleft.x - diff); } } // Wedge is the area to the left of the segment, bounded by // the 45-degree slopes stemming away from the segment's endpoints (e.g. // \_/ for a left-right segment). // In the points in the returned segment, x is the distace from travel.p, // y is distance from bdry (height if it is determined by bdry). // Result is empty or 1 segment. Segment[] wedge_segment (Segment travel, Segment bdry) { int id = bdry.id; Point[] pts = wedge_intersections(travel, bdry); if(pts.length == 0) return new Segment[0]; Point p0 = new Point(pts[0].subtract(travel.p).len(), bdry.ortho_dst(pts[0])); Point p1 = new Point(pts[1].subtract(travel.p).len(), bdry.ortho_dst(pts[1])); Point seg0 = new Point(p0.x < p1.x ? p0 : p1); Point seg1 = new Point(p0.x > p1.x ? p0 : p1); return new Segment[] { new Segment(seg0, seg1, id) }; } // As above, but returns the endpoints with both coordinates original. Point[] wedge_intersections (Segment travel, Segment bdry) { Point sl_prev = new Point(bdry.p); Point sl_next = new Point(bdry.q); if(bdry.is_vertical()) { double diff_y = Math.signum(bdry.q.y - bdry.p.y); sl_prev.y -= diff_y; sl_prev.x -= diff_y; sl_next.y += diff_y; sl_next.x -= diff_y; } else { double diff_x = Math.signum(bdry.q.x - bdry.p.x); sl_prev.y += diff_x; sl_prev.x -= diff_x; sl_next.y += diff_x; sl_next.x += diff_x; } Segment seg_prev = new Segment(bdry.p, sl_prev); Segment seg_next = new Segment(bdry.q, sl_next); Point[] b_inter = intersect(bdry, travel); Point[] p_inter = intersect(seg_prev, travel, true); Point[] n_inter = intersect(seg_next, travel, true); // Travel is on the same line as one of the boundaries of the wedge if(b_inter.length == 2) return b_inter; if(p_inter.length == 2) return p_inter; if(n_inter.length == 2) return n_inter; Point p = new Point(); Point q = new Point(); boolean pin = travel.contains(bdry.p); boolean qin = travel.contains(bdry.q); if(pin && qin) { return new Point[] { bdry.p, bdry.q }; } if(pin || qin) { Point inp = new Point(pin ? bdry.p : bdry.q); if (pin && n_inter.length == 1) { return new Point[] { inp, n_inter[0] }; } if (qin && p_inter.length == 1) { return new Point[] { inp, p_inter[0] }; } // Travel enters/leaves the wedge in inp or only touches if(wedge_contains(bdry, travel.p) && !bdry.p.equals(travel.p) && !bdry.q.equals(travel.p)) return new Point[] { travel.p, inp }; else if(wedge_contains(bdry, travel.q) && !bdry.p.equals(travel.q) && !bdry.q.equals(travel.q)) return new Point[] { travel.q, inp }; else return new Point[0]; } ArrayList inters = new ArrayList(); inters.addAll(Arrays.asList(b_inter)); inters.addAll(Arrays.asList(p_inter)); inters.addAll(Arrays.asList(n_inter)); assert(inters.size() <= 2); if(inters.size() == 0) { if(wedge_contains(bdry, travel.p)) return new Point[] { new Point(travel.p), new Point(travel.q) }; else return new Point[0]; } else if(inters.size() == 1) { if(wedge_contains(bdry, travel.p) && !inters.get(0).equals(travel.p)) return new Point[] { new Point(travel.p), inters.get(0) }; if(wedge_contains(bdry, travel.q) && !inters.get(0).equals(travel.q)) return new Point[] { new Point(travel.q), inters.get(0) }; // Starts on the boundary and goes away return new Point[0]; } else { return new Point[] { inters.get(0), inters.get(1) }; } } // True iff p is inside (or on the boundary). boolean is_in(Segment[] bdry, Point p) { // Find nearest vertical boundary seen when looking to the right from p // and check if p is on its inner side. Segment nearest = new Segment(bdry[0]); boolean found = false; for(Segment bseg : bdry) { if(bseg.is_horizontal()) continue; if(bseg.p.x < p.x) continue; if((bseg.p.y > p.y && bseg.q.y > p.y) || bseg.p.y < p.y && bseg.q.y < p.y) continue; if(!found || nearest.p.x > bseg.p.x) nearest = new Segment(bseg); found = true; } if(!found) return false; return(nearest.ortho_dst(p) >= 0); } ArrayList get_events(ArrayList travelseg) { ArrayList e = new ArrayList(); for(int i=0; i travelseg = new ArrayList(); for(Segment bdseg : bdry) { Segment[] inters = wedge_segment (travel, bdseg); if(inters.length == 1) { travelseg.add(inters[0]); } } ArrayList events = get_events(travelseg); double result = 0; for(int i = 0; i <= events.size(); ++i) { Point pe0 = (i==0 ? new Point(travel.p) : orig_pt(travel, events.get(i-1).p.x)); Point pe1 = (i==events.size() ? new Point(travel.q) : orig_pt(travel, events.get(i).p.x)); if(pe0.x == pe1.x && pe0.y == pe1.y) continue; Point mid = new Point((pe0.x+pe1.x)/2.0, (pe0.y+pe1.y)/2.0); int nearest = nearest_id(bdry, mid); if(nearest >= 0) { pe0.h = bdry[nearest].ortho_dst(pe0); pe1.h = bdry[nearest].ortho_dst(pe1); } double seg_len = pe1.subtract(pe0).len(); result += seg_len; } System.out.println(OUTFORM.format(result)); } public static void main(String[] args) throws IOException { new screamers().run(); } }