QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#268689#5111. Take On MemejuampiRE 0ms0kbJava84.2kb2023-11-28 19:48:572023-11-28 19:48:57

Judging History

你现在查看的是最新测评结果

  • [2023-11-28 19:48:57]
  • 评测
  • 测评结果:RE
  • 用时:0ms
  • 内存:0kb
  • [2023-11-28 19:48:57]
  • 提交

answer

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

class Point {
    int x;
    int y;

    public Point(int x, int y) {
        this.x = x;
        this.y = y;
    }

    public Point negate() {
        return new Point(-x, -y);
    }

    public Point add(Point p) {
        return new Point(x + p.x, y + p.y);
    }

    public Point subtract(Point p) {
        return new Point(x - p.x, y - p.y);
    }

    public void add2(Point p) {
        x += p.x;
        y += p.y;
    }

    public boolean lessThan(Point p, int cmpx, int cmpy) {
        return x * cmpx + y * cmpy < p.x * cmpx + p.y * cmpy;
    }

    public boolean greaterThan(Point p, int cmpx, int cmpy) {
        return x * cmpx + y * cmpy > p.x * cmpx + p.y * cmpy;
    }

    public boolean equals(Point p) {
        return x == p.x && y == p.y;
    }

    public Point ortho() {
        return new Point(-y, x);
    }

    public int lensqr() {
        return x * x + y * y;
    }

    public void print() {
        System.out.println("(" + x + "," + y + ")");
    }

    public Point min(Point other, int cmpx, int cmpy){
        if(this.lessThan(other,cmpx,cmpy)){
          return this;
        }else{
          return other;
        }
    }
    public Point max(Point other, int cmpx, int cmpy){
        if(this.lessThan(other,cmpx,cmpy)){
          return other;
        }else{
          return this;
        }
    }
}

class Main {
    static int cmpx, cmpy, ret;
    static List<List<Integer>> ch;
    static Point[] p;

    public static void main(String[] args) {
        init();
        Scanner scanner = new Scanner(System.in);
        int N = scanner.nextInt();
        scanner.nextLine();  // Consume the newline character

        ch = new ArrayList<>();
        p = new Point[N + 1];
        for (int i = 0; i <= N; i++) {
            ch.add(new ArrayList<>());
        }

        for (int i = 1; i <= N; i++) {
            String[] line = scanner.nextLine().split(" ");
            int M = Integer.parseInt(line[0]);
            if (M == 0) {
                int x = Integer.parseInt(line[1]);
                int y = Integer.parseInt(line[2]);
                p[i] = new Point(x, y);
            } else {
                for (int j = 1; j <= M; j++) {
                    ch.get(i).add(Integer.parseInt(line[j]));
                }
            }
        }
        scanner.close();

        ret = 0;
        Point[] angles = tryAngle(new Point(1, 0));
        Point left = angles[0];
        Point right = angles[1];
        traceHull(left, right);
        traceHull(right, left);

        System.out.println(ret);
    }

    static void init() {
        cmpx = 1;
        cmpy = 0;
        ret = 0;
    }

    static Point[] doit(int x) {
        if (ch.get(x).isEmpty()) {
            return new Point[]{new Point(p[x].x, p[x].y)};
        }

        Point[] result = doit(ch.get(x).get(0));
        Point mntot = result[0];
        Point mxtot = result[1];
        Point mndiff = mxtot.add(mntot);
        Point mxdiff = mndiff;

        for (int i = 1; i < ch.get(x).size(); i++) {
            result = doit(ch.get(x).get(i));
            Point mn = result[0];
            Point mx = result[1];
            mntot = mntot.add(mn);
            mxtot = mxtot.add(mx);
            mndiff = mndiff.min(mx.add(mn),cmpx, cmpy);
            mxdiff = mxdiff.max(mx.add(mn),cmpx, cmpy);
        }

        return new Point[]{mxtot.negate().add(mndiff), mntot.negate().add(mxdiff)};
    }

    static Point[] tryAngle(Point dir) {
        cmpx = dir.x;
        cmpy = dir.y;
        Point[] result = doit(1);

        Point mn = result[0];
        Point mx = result[1];

        ret = Math.max(ret, mn.lensqr());
        ret = Math.max(ret, mx.lensqr());
        return new Point[]{mn, mx};
    }

    static void traceHull(Point a, Point b) {
        if (a.equals(b)) {
            return;
        }
        Point[] result = tryAngle(b.subtract(a).ortho());
        Point c = result[1];

        if (a.lessThan(c, cmpx, cmpy)) {
            traceHull(a, c);
            traceHull(c, b);
        }
    }
}

详细

Test #1:

score: 0
Runtime Error

input:

5
4 2 3 4 5
0 2 -2
0 1 3
0 4 -6
0 -18 5

output:


result: