Untitled
unknown
plain_text
5 months ago
6.6 kB
2
Indexable
import java.util.*; import java.util.function.Function; import java.util.concurrent.atomic.AtomicInteger; class Pt { double x, y; int id; Pt(double x, double y, int id) { this.x = x; this.y = y; this.id = id; } Pt(double x, double y) { this(x, y, -1); } Pt() { this(0, 0, -1); } boolean isEqual(Pt other) { return Math.abs(this.x - other.x) < 1e-9 && Math.abs(this.y - other.y) < 1e-9; } @Override public boolean equals(Object o) { if (this == o) return true; if (o == null || getClass() != o.getClass()) return false; Pt pt = (Pt) o; return Math.abs(x - pt.x) < 1e-9 && Math.abs(y - pt.y) < 1e-9; } @Override public int hashCode() { return Objects.hash(Math.round(x * 1e9), Math.round(y * 1e9)); } } class Seg { Pt start, end; Seg(Pt start, Pt end) { this.start = start; this.end = end; } } public class MaxCycleArea { static int segCount; static List<Pt> pts = new ArrayList<>(); static List<Seg> segs = new ArrayList<>(); static Map<Integer, List<Integer>> adj = new HashMap<>(); static double calcCross(Pt a, Pt b, Pt c) { return (b.x - a.x) * (c.y - a.y) - (b.y - a.y) * (c.x - a.x); } static boolean pointOnSeg(Pt a, Pt b, Pt c) { return b.x <= Math.max(a.x, c.x) + 1e-9 && b.x >= Math.min(a.x, c.x) - 1e-9 && b.y <= Math.max(a.y, c.y) + 1e-9 && b.y >= Math.min(a.y, c.y) - 1e-9; } static boolean segIntersect(Pt a1, Pt a2, Pt b1, Pt b2) { double c1 = calcCross(a1, a2, b1); double c2 = calcCross(a1, a2, b2); double c3 = calcCross(b1, b2, a1); double c4 = calcCross(b1, b2, a2); if (c1 * c2 < -1e-9 && c3 * c4 < -1e-9) return true; if (Math.abs(c1) < 1e-9 && pointOnSeg(a1, b1, a2)) return true; if (Math.abs(c2) < 1e-9 && pointOnSeg(a1, b2, a2)) return true; if (Math.abs(c3) < 1e-9 && pointOnSeg(b1, a1, b2)) return true; if (Math.abs(c4) < 1e-9 && pointOnSeg(b1, a2, b2)) return true; return false; } static Pt findIntersect(Pt a1, Pt a2, Pt b1, Pt b2) { double a = a2.y - a1.y; double b = a1.x - a2.x; double c = a * a1.x + b * a1.y; double p = b2.y - b1.y; double q = b1.x - b2.x; double r = p * b1.x + q * b1.y; double det = a * q - p * b; if (Math.abs(det) < 1e-9) { return new Pt(); } else { double x = (q * c - b * r) / det; double y = (a * r - p * c) / det; return new Pt(x, y); } } public static void main(String[] args) { Scanner sc = new Scanner(System.in); segCount = sc.nextInt(); AtomicInteger ptId = new AtomicInteger(0); Map<Pt, Integer> ptMap = new HashMap<>(); for (int i = 0; i < segCount; i++) { Pt p1 = new Pt(sc.nextInt(), sc.nextInt(), 0); Pt p2 = new Pt(sc.nextInt(), sc.nextInt(), 0); p1.id = ptMap.computeIfAbsent(p1, k -> ptId.getAndIncrement()); p2.id = ptMap.computeIfAbsent(p2, k -> ptId.getAndIncrement()); if (p1.id == pts.size()) pts.add(p1); if (p2.id == pts.size()) pts.add(p2); segs.add(new Seg(p1, p2)); } for (int i = 0; i < segs.size(); i++) { for (int j = i + 1; j < segs.size(); j++) { if (segIntersect(segs.get(i).start, segs.get(i).end, segs.get(j).start, segs.get(j).end)) { Pt ip = findIntersect(segs.get(i).start, segs.get(i).end, segs.get(j).start, segs.get(j).end); ip.id = ptMap.computeIfAbsent(ip, k -> ptId.getAndIncrement()); if (ip.id == pts.size()) pts.add(ip); } } } for (Seg s : segs) { List<Pt> ptsOnSeg = new ArrayList<>(); for (Pt p : pts) { if (pointOnSeg(s.start, p, s.end) && Math.abs(calcCross(s.start, s.end, p)) < 1e-9) { ptsOnSeg.add(p); } } ptsOnSeg.sort(Comparator.comparingDouble( p -> Math.hypot(p.x - s.start.x, p.y - s.start.y) )); for (int i = 0; i < ptsOnSeg.size() - 1; i++) { int u = ptsOnSeg.get(i).id; int v = ptsOnSeg.get(i + 1).id; adj.computeIfAbsent(u, k -> new ArrayList<>()).add(v); adj.computeIfAbsent(v, k -> new ArrayList<>()).add(u); } } Set<List<Integer>> cycles = new HashSet<>(); int maxCycleArea = 0; Function<Void, Void> detectCycles = unused -> { for (int i = 0; i < pts.size(); i++) { List<Integer> path = new ArrayList<>(); Set<Integer> vis = new HashSet<>(); findCycles(i, i, path, vis, cycles); } return null; }; detectCycles.apply(null); for (List<Integer> cycle : cycles) { double area = 0; for (int i = 0; i < cycle.size(); i++) { Pt p1 = pts.get(cycle.get(i)); Pt p2 = pts.get(cycle.get((i + 1) % cycle.size())); area += (p1.x * p2.y - p2.x * p1.y); } area = Math.abs(area) / 2.0; maxCycleArea = Math.max(maxCycleArea, (int) Math.round(area)); } System.out.println(maxCycleArea); } static void findCycles(int start, int curr, List<Integer> path, Set<Integer> vis, Set<List<Integer>> cycles) { vis.add(curr); path.add(curr); for (int next : adj.getOrDefault(curr, new ArrayList<>())) { if (next == start && path.size() >= 3) { List<Integer> cycle = new ArrayList<>(path); int minIdx = cycle.indexOf(Collections.min(cycle)); Collections.rotate(cycle, -minIdx); if (calcCross(pts.get(cycle.get(0)), pts.get(cycle.get(1)), pts.get(cycle.get(2))) < 0) { Collections.reverse(cycle); } cycles.add(cycle); } else if (!vis.contains(next)) { findCycles(start, next, path, vis, cycles); } } vis.remove(curr); path.remove(path.size() - 1); } }
Editor is loading...
Leave a Comment