提出 #64986282

---

ソースコード 拡げる

import java.io.*;
import java.nio.file.Files;
import java.nio.file.Path;
import java.util.*;
import java.util.function.Predicate;
import java.util.stream.Collectors;

public class Main {
    static InputStream is;
    static PrintWriter out;
    static String INPUT = "";
    static SplittableRandom gen = new SplittableRandom(114514810);

    static int X, Y, Z;
    static final boolean debug = false;

    public Main() throws IOException, FileNotFoundException {
    }

    static class SubProblem {
        List<Integer> org_row_idx_first;
        List<Integer> org_row_idx_second;
        long first_co[][];
        long second_co[][];

        SubProblem(
                List<Integer> org_row_idx_first,
                List<Integer> org_row_idx_second,
                long first_co[][],
                long second_co[][]
        ) {
            this.org_row_idx_first = org_row_idx_first;
            this.org_row_idx_second = org_row_idx_second;
            this.first_co = first_co;
            this.second_co = second_co;
        }

        long balance(){
            long ans = 0;
            for(int i = 0 ; i < first_co.length ; i++){
                for(int j = 0 ; j < first_co.length ; j++){
                    ans += (first_co[i][0] - first_co[j][0]) * (first_co[i][0] - first_co[j][0]) + (first_co[i][1] - first_co[j][1]) * (first_co[i][1] - first_co[j][1]);
                }
            }
            for(int i = 0 ; i < second_co.length ; i++){
                for(int j = 0 ; j < second_co.length ; j++){
                    ans += (second_co[i][0] - second_co[j][0]) * (second_co[i][0] - second_co[j][0]) + (second_co[i][1] - second_co[j][1]) * (second_co[i][1] - second_co[j][1]);
                }
            }
            return ans;
        }

        static SubProblem split(long cox[][], Predicate<long[]> predicate) {
            List<long[]> first = new ArrayList<>();
            List<long[]> second = new ArrayList<>();
            List<Integer> org_row_idx_first = new ArrayList<>();
            List<Integer> org_row_idx_second = new ArrayList<>();

            for (int i = 0; i < cox.length; i++) {
                if (predicate.test(cox[i])) {
                    org_row_idx_first.add(i);
                    first.add(cox[i]);
                } else {
                    org_row_idx_second.add(i);
                    second.add(cox[i]);
                }
            }
            return new SubProblem(org_row_idx_first, org_row_idx_second, first.toArray(new long[0][]), second.toArray(new long[0][]));
        }
    }

    static long[][] append(long[][] org, long[] p1, long[] p2){
        long[][] ans = new long[org.length+2][2];
        for(int i = 0 ; i < org.length ; i++)
            ans[i] = org[i];
        ans[org.length] = p1;
        ans[org.length+1] = p2;
        return ans;
    }

    // 2点を持って貪欲
    static void solve() {

        long S = System.currentTimeMillis();
        X = ni();
        Y = ni();
        Z = ni();
        long[][] cox, coy, coz;
        cox = nml(X, 2);
        coy = nml(Y, 2);
        coz = nml(Z, 2);


        SubProblem xSub = null;
        SubProblem ySub = null;

        for(int i = 0 ; i < 1000 ; i++){
            // Generate two random points with coordinates less than 1000000
            long[] p1 = new long[]{gen.nextInt(1000000), gen.nextInt(1000000)};
            long[] p2 = new long[]{gen.nextInt(1000000), gen.nextInt(1000000)};

            // Use cross product (orient function) to determine which side of the line each point falls on
            SubProblem xSub_ = SubProblem.split(cox, (co) -> orient(p1, p2, co) > 0);
            SubProblem ySub_ = SubProblem.split(coy, (co) -> orient(p1, p2, co) < 0);

            if( xSub == null || xSub_.balance() + ySub_.balance() < xSub.balance() + ySub.balance() ) {
                xSub = xSub_;
                ySub = ySub_;
                System.err.println(xSub.first_co.length + " " + xSub.second_co.length + "|" + ySub.first_co.length + " " + ySub.second_co.length);
            }
        }


        assert Y == 0;

        Result bestA = null;
        long rep = 0;
        while (System.currentTimeMillis() - S < 900) {
            rep++;
            Result res = greedy_solve(bestA != null && bestA.count == xSub.first_co.length ? bestA.time : 1.5e7, xSub.first_co, coy, coz, xSub.org_row_idx_first, -1, -1);
            if (bestA == null || bestA.count < res.count || (bestA.count == res.count && bestA.time > res.time)) {
                bestA = res;
                System.err.println(bestA.time);
            }
        }

        Result bestB = null;
        while (System.currentTimeMillis() - S < 1800) {
            rep++;
            Result res = greedy_solve(bestB != null && bestB.count == ySub.first_co.length  ? bestB.time : 1.5e7, ySub.first_co, cox, coz, ySub.org_row_idx_first, -1, -1);
            if (bestB == null || bestB.count < res.count || (bestB.count == res.count && bestB.time > res.time)) {
                bestB = res;
                System.err.println(bestB.time);

            }
        }

        MergedResult firstBest = new MergedResult(bestA, bestB, cox, coy);

        xSub.org_row_idx_second.add(bestA.route.get(bestA.route.size()-2));
        xSub.org_row_idx_second.add(bestA.route.get(bestA.route.size()-1));
        Result easyA = greedy_solve(1.5e7, append(xSub.second_co, cox[bestA.route.get(bestA.route.size()-2)], cox[bestA.route.get(bestA.route.size()-1)]), ySub.second_co, new long[0][], xSub.org_row_idx_second, xSub.second_co.length, xSub.second_co.length+1);
        ySub.org_row_idx_second.add(bestB.route.get(bestB.route.size()-2));
        ySub.org_row_idx_second.add(bestB.route.get(bestB.route.size()-1));
        Result easyB = greedy_solve(1.5e7, append(ySub.second_co, coy[bestB.route.get(bestB.route.size()-2)], coy[bestB.route.get(bestB.route.size()-1)]), xSub.second_co , new long[0][], ySub.org_row_idx_second, ySub.second_co.length, ySub.second_co.length+1);

        MergedResult second = new MergedResult(easyA, easyB, cox, coy);


        if (debug) {
            tr("best.time", bestA.time);
            tr("best.count", bestA.count);
            tr("rep", rep);
            tr("steps", steps);
        } else {
            firstBest.show();;
            second.show();;
        }
    }

    static class Result {
        List<Integer> route;
        double time;
        int count;

        public Result(List<Integer> route, double time, int count, List<Integer> idxMap) {
            this.route = route.stream().map(r -> idxMap.get(r)).collect(Collectors.toList());
            this.time = time;
            this.count = count;
        }

    }

    static class MergedResult {
        long[][] output;
        double time;
        int count;

        public MergedResult(final Result x, final Result y, long cox[][], long coy[][]) {
            assert x.route.size() % 2 == 0;
            assert y.route.size() % 2 == 0;

            long[][] output = new long[Math.max(x.route.size() / 2, y.route.size() / 2)][8];
            int lastIndex_X = -1;
            int lastIndex_Y = -1;

            for (int i = 0; i < output.length; i++) {
                if (i * 2 + 1 < x.route.size()) {
                    int a = x.route.get(i * 2);
                    int b = x.route.get(i * 2 + 1);
                    output[i][0] = cox[a][0];
                    output[i][1] = cox[a][1];
                    output[i][2] = cox[b][0];
                    output[i][3] = cox[b][1];
                    lastIndex_X = i;
                } else {
                    output[i][0] = output[lastIndex_X][0];
                    output[i][1] = output[lastIndex_X][1];
                    output[i][2] = output[lastIndex_X][2];
                    output[i][3] = output[lastIndex_X][3];
                }

                if (i * 2 + 1 < y.route.size()) {
                    int a = y.route.get(i * 2);
                    int b = y.route.get(i * 2 + 1);
                    output[i][4] = coy[a][0];
                    output[i][5] = coy[a][1];
                    output[i][6] = coy[b][0];
                    output[i][7] = coy[b][1];
                    lastIndex_Y = i;
                } else {
                    output[i][4] = output[lastIndex_Y][4];
                    output[i][5] = output[lastIndex_Y][5];
                    output[i][6] = output[lastIndex_Y][6];
                    output[i][7] = output[lastIndex_Y][7];
                }
            }

            double score = 0;
            for (int i = 0; i + 1 < output.length; i++) {
                double aa = Math.sqrt(d2(new long[]{output[i][0], output[i][1]}, new long[]{output[i + 1][0], output[i + 1][1]}));
                double bb = Math.sqrt(d2(new long[]{output[i][2], output[i][3]}, new long[]{output[i + 1][2], output[i + 1][3]}));
                double cc = Math.sqrt(d2(new long[]{output[i][4], output[i][5]}, new long[]{output[i + 1][4], output[i + 1][5]}));
                double dd = Math.sqrt(d2(new long[]{output[i][6], output[i][7]}, new long[]{output[i + 1][6], output[i + 1][7]}));
                score += Math.max(aa + bb, cc + dd);
            }
            this.time = score;
            this.output = output;
            this.count = x.count + y.count;
        }

        void show() {
            for (int i = 0; i < output.length; i++) {
                out.println(Arrays.stream(output[i]).mapToObj(e -> String.valueOf(e)).collect(Collectors.joining(" ")));
            }

        }
    }

    static long steps = 0;

    static Result greedy_solve(double lim, long[][] cox, long[][] coy, long[][] coz, List<Integer> orgIdxMap,int L,int R) {
        int X = cox.length;
        int Y = coy.length;
        int Z = coz.length;

        List<Integer> route = new ArrayList<>();

        boolean[] ved = new boolean[X];
        int l = gen.nextInt(X);
        int r = gen.nextInt(X);
        if( L != -1 ) l = L;
        if( R != -1 ) r = R;

        ved[l] = ved[r] = true;
        route.add(l);
        route.add(r);
        double time = 0;
//		int side = 0;
        while (!allTrue(ved) && time <= lim) {
            int argi = -1;
            int argp = -1;
            double argt = 0;
            double argpdt = -1;
            inner:
            for (int i = 0; i < X; i++) {
                if (i == l) continue;
                // 障害物を通らないこと
                for (int k = 0; k < Z; k++) {
                    if (contains(coz[k], cox[l], cox[r], cox[i])) {
                        continue inner;
                    }
                }
                for (int k = 0; k < Y; k++) {
                    if (contains(coy[k], cox[l], cox[r], cox[i])) {
                        continue inner;
                    }
                }
                int plus = 0;
                double dt = Math.sqrt(d2(cox[l], cox[i]));
                if (time + dt >= lim) continue;
                for (int k = 0; k < X; k++) {
                    if (ved[k]) continue;
                    steps++;
                    if (contains(cox[k], cox[l], cox[r], cox[i])) {
                        plus += 1;
                    }
                }
                double pdt = plus / dt;

                if (pdt > argpdt || (pdt == argpdt && plus > argp) || (pdt == argpdt && plus == argp && dt < argt)) {
                    argi = i;
                    argp = plus;
                    argt = dt;
                    argpdt = pdt;
                }
            }
            if (argi == -1) break;

            for (int k = 0; k < X; k++) {
                if (ved[k]) continue;
                if (contains(cox[k], cox[l], cox[r], cox[argi])) {
                    ved[k] = true;
                }
            }
//			tr(l, r, argi, argt);

            l = r;
            r = argi;
            time += argt;
            route.add(argi);
        }
        if (route.size() % 2 == 1) {
            route.add(route.get(route.size() - 2));
        }

//		tr(count(ved));
        return new Result(route, time, count(ved), orgIdxMap);
    }


    static long d2(long[] a, long[] b) {
        return (a[0] - b[0]) * (a[0] - b[0]) + (a[1] - b[1]) * (a[1] - b[1]);
    }

    static int count(boolean[] b) {
        int count = 0;
        for (boolean bb : b) {
            if (bb) count++;
        }
        return count;
    }

    static boolean allTrue(boolean[] b) {
        for (boolean bb : b) {
            if (!bb) return false;
        }
        return true;
    }

    // 2D orientation: positive if p is to the left of the line a→b, negative if to the right, zero if colinear
    public static long orient(long[] a, long[] b, long[] p) {
        return (b[0] - a[0]) * (p[1] - a[1]) - (b[1] - a[1]) * (p[0] - a[0]);
    }

    // Check if point p is inside triangle abc or on its boundary
    public static boolean contains(long[] p, long[] a, long[] b, long[] c) {
        // Degenerate case: triangle is colinear
        if (orient(a, b, c) == 0) {
            if (orient(a, b, p) != 0 || orient(a, c, p) != 0) {
                return false;
            }
            long minX = Math.min(a[0], Math.min(b[0], c[0]));
            long maxX = Math.max(a[0], Math.max(b[0], c[0]));
            long minY = Math.min(a[1], Math.min(b[1], c[1]));
            long maxY = Math.max(a[1], Math.max(b[1], c[1]));
            return minX <= p[0] && p[0] <= maxX && minY <= p[1] && p[1] <= maxY;
        }

        // Non-degenerate triangle: check that p lies on the same side of all edges
        long c1 = orient(a, b, p);
        long c2 = orient(b, c, p);
        long c3 = orient(c, a, p);
        return (c1 >= 0 && c2 >= 0 && c3 >= 0) || (c1 <= 0 && c2 <= 0 && c3 <= 0);
    }


    public static void main(String[] args) throws Exception {
        long S = System.currentTimeMillis();
        is = INPUT.isEmpty() ? System.in : new ByteArrayInputStream(INPUT.getBytes());
        out = new PrintWriter(System.out);
        if (Files.exists(Path.of("/home/kyuridenamida/masters-2025-final/kyuridenamida/sol/in.txt"))) {
            is = new FileInputStream("/home/kyuridenamida/masters-2025-final/kyuridenamida/sol/in.txt");
            out = new PrintWriter(new FileOutputStream("/home/kyuridenamida/masters-2025-final/kyuridenamida/sol/out.txt"));
        }

        solve();
        out.flush();
        long G = System.currentTimeMillis();
        tr(G - S + "ms");
    }

    private static boolean eof() {
        if (lenbuf == -1) return true;
        int lptr = ptrbuf;
        while (lptr < lenbuf) if (!isSpaceChar(inbuf[lptr++])) return false;

        try {
            is.mark(1000);
            while (true) {
                int b = is.read();
                if (b == -1) {
                    is.reset();
                    return true;
                } else if (!isSpaceChar(b)) {
                    is.reset();
                    return false;
                }
            }
        } catch (IOException e) {
            return true;
        }
    }

    private static byte[] inbuf = new byte[1024];
    static int lenbuf = 0, ptrbuf = 0;

    private static int readByte() {
        if (lenbuf == -1) throw new InputMismatchException();
        if (ptrbuf >= lenbuf) {
            ptrbuf = 0;
            try {
                lenbuf = is.read(inbuf);
            } catch (IOException e) {
                throw new InputMismatchException();
            }
            if (lenbuf <= 0) return -1;
        }
        return inbuf[ptrbuf++];
    }

    private static boolean isSpaceChar(int c) {
        return !(c >= 33 && c <= 126);
    }

    //	private static boolean isSpaceChar(int c) { return !(c >= 32 && c <= 126); }
    private static int skip() {
        int b;
        while ((b = readByte()) != -1 && isSpaceChar(b)) ;
        return b;
    }

    private static double nd() {
        return Double.parseDouble(ns());
    }

    private static char nc() {
        return (char) skip();
    }

    private static String ns() {
        int b = skip();
        StringBuilder sb = new StringBuilder();
        while (!(isSpaceChar(b))) {
            sb.appendCodePoint(b);
            b = readByte();
        }
        return sb.toString();
    }

    private static char[] ns(int n) {
        char[] buf = new char[n];
        int b = skip(), p = 0;
        while (p < n && !(isSpaceChar(b))) {
            buf[p++] = (char) b;
            b = readByte();
        }
        return n == p ? buf : Arrays.copyOf(buf, p);
    }

    private static char[][] nm(int n, int m) {
        char[][] map = new char[n][];
        for (int i = 0; i < n; i++) map[i] = ns(m);
        return map;
    }

    private static int[][] nmi(int n, int m) {
        int[][] map = new int[n][];
        for (int i = 0; i < n; i++) map[i] = na(m);
        return map;
    }

    private static long[][] nml(int n, int m) {
        long[][] map = new long[n][];
        for (int i = 0; i < n; i++) map[i] = nal(m);
        return map;
    }

    private static int[] na(int n) {
        int[] a = new int[n];
        for (int i = 0; i < n; i++) a[i] = ni();
        return a;
    }

    private static long[] nal(int n) {
        long[] a = new long[n];
        for (int i = 0; i < n; i++) a[i] = nl();
        return a;
    }

    private static int ni() {
        int num = 0, b;
        boolean minus = false;
        while ((b = readByte()) != -1 && !((b >= '0' && b <= '9') || b == '-')) ;
        if (b == '-') {
            minus = true;
            b = readByte();
        }

        while (true) {
            if (b >= '0' && b <= '9') {
                num = num * 10 + (b - '0');
            } else {
                return minus ? -num : num;
            }
            b = readByte();
        }
    }

    private static long nl() {
        long num = 0;
        int b;
        boolean minus = false;
        while ((b = readByte()) != -1 && !((b >= '0' && b <= '9') || b == '-')) ;
        if (b == '-') {
            minus = true;
            b = readByte();
        }

        while (true) {
            if (b >= '0' && b <= '9') {
                num = num * 10 + (b - '0');
            } else {
                return minus ? -num : num;
            }
            b = readByte();
        }
    }

    private static void tr(Object... o) {
        if (INPUT.length() != 0) System.out.println(Arrays.deepToString(o));
    }
}

提出情報

ジャッジ結果