Untitled

 avatar
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