QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#268689 | #5111. Take On Meme | juampi | RE | 0ms | 0kb | Java8 | 4.2kb | 2023-11-28 19:48:57 | 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