QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#268657#5111. Take On MemejuampiCompile Error//Python33.9kb2023-11-28 19:30:272023-11-28 19:30:27

Judging History

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

  • [2023-11-28 19:30:27]
  • 评测
  • [2023-11-28 19:30:27]
  • 提交

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 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.subtract();
        Point right = angles.add();
        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(p[x].x, p[x].y);
        }

        Point result = doit(ch.get(x).get(0));
        Point mntot = new Point(result.x, result.y);
        Point mxtot = new Point(result.x, result.y);
        int mndiff = mxtot.lensqr() + mntot.lensqr();
        int mxdiff = mndiff;

        for (int i = 1; i < ch.get(x).size(); i++) {
            result = doit(ch.get(x).get(i));
            Point mn = new Point(result.x, result.y);
            Point mx = new Point(result.x, result.y);
            mntot = mntot.add(mn);
            mxtot = mxtot.add(mx);
            mndiff = Math.min(mndiff, mx.lensqr() + mn.lensqr());
            mxdiff = Math.max(mxdiff, mx.lensqr() + mn.lensqr());
        }

        return new Point(-mxtot.x + mndiff, -mntot.x + mxdiff);
    }

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

        Point mn = new Point(result.x, result.y);
        Point mx = new Point(result.x, result.y);

        ret = Math.max(ret, mn.lensqr());
        ret = Math.max(ret, mx.lensqr());
        return mn;
    }

    static void traceHull(Point a, Point b) {
        if (a.equals(b)) {
            return;
        }
        Point result = tryAngle(b.subtract(a).ortho());
        Point c = new Point(result.x, result.y);

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

Details

  File "answer.code", line 5
    class Point {
                ^
SyntaxError: invalid syntax