結果
| 問題 | No.2012 Largest Triangle |
| ユーザー |
 Yu_212
|
| 提出日時 | 2022-07-15 23:08:03 |
| 言語 | Java21 (openjdk 21) |
| 結果 |
AC
|
| 実行時間 | 878 ms / 2,500 ms |
| コード長 | 24,298 bytes |
| コンパイル時間 | 4,842 ms |
| コンパイル使用メモリ | 105,348 KB |
| 実行使用メモリ | 77,468 KB |
| 最終ジャッジ日時 | 2023-09-10 05:50:18 |
| 合計ジャッジ時間 | 24,737 ms |
|
ジャッジサーバーID （参考情報） |
judge15 / judge12 |
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| testcase_00 | AC | 67 ms
50,992 KB |
| testcase_01 | AC | 68 ms
50,836 KB |
| testcase_02 | AC | 67 ms
50,700 KB |
| testcase_03 | AC | 69 ms
50,792 KB |
| testcase_04 | AC | 69 ms
51,124 KB |
| testcase_05 | AC | 69 ms
50,832 KB |
| testcase_06 | AC | 68 ms
50,856 KB |
| testcase_07 | AC | 69 ms
50,892 KB |
| testcase_08 | AC | 69 ms
50,828 KB |
| testcase_09 | AC | 70 ms
50,916 KB |
| testcase_10 | AC | 70 ms
50,932 KB |
| testcase_11 | AC | 77 ms
51,924 KB |
| testcase_12 | AC | 73 ms
51,904 KB |
| testcase_13 | AC | 72 ms
50,792 KB |
| testcase_14 | AC | 73 ms
51,808 KB |
| testcase_15 | AC | 74 ms
51,836 KB |
| testcase_16 | AC | 710 ms
76,760 KB |
| testcase_17 | AC | 799 ms
76,592 KB |
| testcase_18 | AC | 714 ms
76,980 KB |
| testcase_19 | AC | 725 ms
77,024 KB |
| testcase_20 | AC | 717 ms
76,972 KB |
| testcase_21 | AC | 710 ms
76,992 KB |
| testcase_22 | AC | 694 ms
76,684 KB |
| testcase_23 | AC | 695 ms
77,152 KB |
| testcase_24 | AC | 712 ms
76,860 KB |
| testcase_25 | AC | 668 ms
77,104 KB |
| testcase_26 | AC | 850 ms
76,752 KB |
| testcase_27 | AC | 862 ms
72,396 KB |
| testcase_28 | AC | 841 ms
75,188 KB |
| testcase_29 | AC | 862 ms
77,044 KB |
| testcase_30 | AC | 878 ms
77,208 KB |
| testcase_31 | AC | 779 ms
74,796 KB |
| testcase_32 | AC | 753 ms
72,940 KB |
| testcase_33 | AC | 803 ms
76,824 KB |
| testcase_34 | AC | 793 ms
77,032 KB |
| testcase_35 | AC | 760 ms
77,468 KB |
| testcase_36 | AC | 87 ms
53,236 KB |
| testcase_37 | AC | 88 ms
52,968 KB |
| testcase_38 | AC | 88 ms
52,672 KB |
| testcase_39 | AC | 88 ms
52,744 KB |
| testcase_40 | AC | 88 ms
51,148 KB |
| testcase_41 | AC | 256 ms
60,000 KB |
ソースコード
import java.io.*;
import java.util.*;
import java.util.function.IntUnaryOperator;
import java.util.function.LongUnaryOperator;
import java.util.stream.Collectors;
public class Main {
static In in = new FastIn();
static Out out = new Out(false);
static final long inf = 0x1fffffffffffffffL;
static final int iinf = 0x3fffffff;
static final double eps = 1e-7;
static long mod = 998244353;
long[] x;
long[] y;
Geometry.Point[] p;
void solve() {
int n = in.nextInt();
Geometry.Point[] ps = new Geometry.Point[n];
x = new long[n];
y = new long[n];
for (int i = 0; i < n; i++) {
x[i] = in.nextInt();
y[i] = in.nextInt();
}
for (int i = 0; i < n; i++) {
ps[i] = new Geometry.Point(x[i], y[i]);
}
p = new Geometry.Polygon(ps).convexHull().vertices;
long max = 0;
for (int i = 0; i < n; i++) {
if (n < 100) {
for (int j = 0; j < n; j++) {
max = Math.max(max, x[i] * y[j] - y[i] * x[j]);
}
continue;
}
int l = 0;
int r = p.length - 1;
max = Math.max(max, val(i, l));
max = Math.max(max, val(i, r));
boolean bb = true;
while (r - l > 100) {
int lm = l + (r - l) / 3;
int rm = r - (r - l) / 3;
long lv = val(i, lm);
long rv = val(i, rm);
max = Math.max(max, lv);
max = Math.max(max, rv);
if (lv == rv) {
max = Math.max(max, check(i, 0, lm));
max = Math.max(max, check(i, lm, rm));
max = Math.max(max, check(i, rm, p.length - 1));
bb = false;
break;
}
if (lv > rv) {
r = rm;
} else {
l = lm;
}
}
if (bb) {
for (int j = l; j <= r; j++) {
max = Math.max(max, val(i, j));
}
}
}
out.println(max);
}
long val(int i, int pj) {
return x[i] * ((long)p[pj].y) - y[i] * ((long)p[pj].x);
}
long check(int i, int l, int r) {
long lv = val(i, l);
long rv = val(i, r);
long max = 0;
max = Math.max(max, lv);
max = Math.max(max, rv);
while (r - l > 100) {
int lm = l + (r - l) / 3;
int rm = r - (r - l) / 3;
lv = val(i, lm);
rv = val(i, rm);
max = Math.max(max, lv);
max = Math.max(max, rv);
if (lv > rv) {
r = rm;
} else {
l = lm;
}
}
for (int j = l; j <= r; j++) {
max = Math.max(max, val(i, j));
}
return max;
}
public static void main(String... args) {
new Main().solve();
out.flush();
}
}
class Geometry {
static final int OUT = -1;
static final int ON = 0;
static final int IN = 1;
static final int COUNTER_CLOCKWISE = 1;
static final int CLOCKWISE = -1;
static final int BACK = 2;
static final int FRONT = -2;
static class Point {
static final Comparator<Point> XY_ORDER = (a, b) -> compare(a.x, b.x) == 0 ? compare(a.y, b.y) : compare(a.x, b.x);
static final Comparator<Point> YX_ORDER = (a, b) -> compare(a.y, b.y) == 0 ? compare(a.x, b.x) : compare(a.y, b.y);
static final Comparator<Point> ARG_ORDER = (a, b) -> compareArgument(a.x, a.y, b.x, b.y);
final double x;
final double y;
Point(double x, double y) {
this.x = x;
this.y = y;
}
static Point polar(double r, double a) {
return new Point(Math.cos(a) * r, Math.sin(a) * r);
}
Point add(Point o) {
return new Point(x + o.x, y + o.y);
}
Point subtract(Point o) {
return new Point(x - o.x, y - o.y);
}
Point multiply(double k) {
return new Point(x * k, y * k);
}
Point divide(double k) {
return new Point(x / k, y / k);
}
double norm() {
return x * x + y * y;
}
double abs() {
return Math.hypot(x, y);
}
// 内積
double dot(Point o) {
return x * o.x + y * o.y;
}
// 外積
double cross(Point o) {
return x * o.y - y * o.x;
}
double arg() {
return Math.atan2(y, x);
}
// 象限
int orthant() {
return y >= 0 ? x >= 0 ? 0 : 1 : x >= 0 ? 3 : 2;
}
// 並行判定
boolean isParallel(Point o) {
return sign(cross(o)) == 0;
}
// 直交判定
boolean isOrthogonal(Point o) {
return sign(dot(o)) == 0;
}
@Override
public String toString() {
return "{" + x + ", " + y + "}";
}
}
static class Segment {
final Point p1;
final Point p2;
Segment(Point p1, Point p2) {
this.p1 = p1;
this.p2 = p2;
}
Line toLine() {
return new Line(p1, p2);
}
Point projection(Point p) {
return toLine().projection(p);
}
boolean intersect(Segment s) {
return ccw(p1, p2, s.p1) * ccw(p1, p2, s.p2) <= 0 && ccw(s.p1, s.p2, p1) * ccw(s.p1, s.p2, p2) <= 0;
}
double distance(Point p) {
if (sign(p2.subtract(p1).dot(p.subtract(p1))) < 0) {
return p.subtract(p1).abs();
}
if (sign(p1.subtract(p2).dot(p.subtract(p2))) < 0) {
return p.subtract(p2).abs();
}
return toLine().distance(p);
}
double distance(Segment s) {
if (intersect(s)) {
return 0;
}
double dist1 = Math.min(distance(s.p1), distance(s.p2));
double dist2 = Math.min(s.distance(p1), s.distance(p2));
return Math.min(dist1, dist2);
}
@Override
public String toString() {
return "{" + p1 + " -> " + p2 + "}";
}
}
static class Line {
final Point p1;
final Point p2;
Line(Point p1, Point p2) {
this.p1 = p1;
this.p2 = p2;
}
Segment toSegment() {
return new Segment(p1, p2);
}
Point projection(Point p) {
Point base = p2.subtract(p1);
double r = p.subtract(p1).dot(base) / base.norm();
return p1.add(base.multiply(r));
}
Point reflection(Point p) {
return projection(p).subtract(p).multiply(2).add(p);
}
// 並行判定
boolean isParallel(Line l) {
return sign(p2.subtract(p1).cross(l.p2.subtract(l.p1))) == 0;
}
// 直交判定
boolean isOrthogonal(Line l) {
return sign(p2.subtract(p1).dot(l.p2.subtract(l.p1))) == 0;
}
boolean intersect(Segment s) {
double a = p2.subtract(p1).cross(s.p1.subtract(p1));
double b = p2.subtract(p1).cross(s.p2.subtract(p1));
return sign(a * b) <= 0;
}
boolean intersect(Line l) {
return !isParallel(l);
}
double distance(Point p) {
return Math.abs(p2.subtract(p1).cross(p.subtract(p1)) / p2.subtract(p1).abs());
}
double distance(Segment s) {
return intersect(s) ? 0 : Math.min(distance(s.p1), distance(s.p2));
}
double distance(Line l) {
return intersect(l) ? 0 : distance(l.p1);
}
Point crossPoint(Line l) {
double a = p2.subtract(p1).cross(l.p2.subtract(l.p1));
double b = p2.subtract(p1).cross(p2.subtract(l.p1));
if (sign(a) == 0 && sign(b) == 0) {
return l.p1;
}
return l.p2.subtract(l.p1).multiply(b / a).add(l.p1);
}
@Override
public String toString() {
return "{" + p1 + " -> " + p2 + "}";
}
}
static class Circle {
final Point c;
final double r;
Circle(Point c, double r) {
this.c = c;
this.r = r;
}
// 交点の数
int intersect(Segment s) {
Point h = s.projection(c);
if (sign(h.subtract(c).norm() - r * r) > 0) {
return 0;
}
double d1 = c.subtract(s.p1).abs();
double d2 = c.subtract(s.p2).abs();
if (compare(d1, r) <= 0 && compare(d2, r) <= 0) {
return 0;
}
if (compare(d1, r) < 0 && compare(d2, r) > 0) {
return 1;
}
if (compare(d1, r) > 0 && compare(d2, r) < 0) {
return 1;
}
if (sign(s.p1.subtract(h).dot(s.p2.subtract(h))) < 0) {
return 2;
}
return 0;
}
int intersect(Line l) {
int comp = compare(l.distance(c), r);
return comp < 0 ? 2 : comp == 0 ? 1 : 0;
}
// 共通接線の数
int intersect(Circle c) {
Circle small = r < c.r ? this : c;
Circle large = r < c.r ? c : this;
double d = large.c.subtract(small.c).abs();
double r = small.r + large.r;
if (compare(d, r) == 0) {
return 3; // 外接する
} else if (d > r) {
return 4; // 離れている
} else if (compare(d + small.r, large.r) == 0) {
return 1; // 内接する
} else if (compare(d + small.r, large.r) < 0) {
return 0; // 内包する
} else {
return 2; // 交わる
}
}
Point[] crossPoint(Line l) {
Point p = l.projection(c);
Point e = l.p2.subtract(l.p1).divide(l.p2.subtract(l.p1).abs());
if (compare(l.distance(c), r) == 0) {
return new Point[] {p, p};
}
Point m = e.multiply(Math.sqrt(r * r - p.subtract(c).norm()));
return new Point[] {p.add(m), p.subtract(m)};
}
Point[] crossPoint(Segment s) {
Point[] points = crossPoint(s.toLine());
if (intersect(s) == 2) {
return points;
}
if (sign(s.p1.subtract(points[0]).dot(s.p2.subtract(points[0]))) < 0) {
return new Point[] {points[0]};
} else {
return new Point[] {points[1]};
}
}
Point[] crossPoint(Circle o) {
double d = c.subtract(o.c).abs();
double a = Math.acos((r * r + d * d - o.r * o.r) / (2 * r * d));
double t = o.c.subtract(c).arg();
return new Point[] {Point.polar(r, t + a).add(c), Point.polar(r, t - a).add(c)};
}
int contains(Point p) {
return compare(r * r, c.subtract(p).norm());
}
@Override
public String toString() {
return "{" + c + ", " + r + "}";
}
}
static class Polygon {
final Point[] vertices;
Polygon(Point[] vertices) {
this.vertices = vertices;
}
Polygon(List<Point> vertices) {
this.vertices = vertices.toArray(new Point[0]);
}
Polygon convexHull() {
Point[] points = Arrays.copyOf(vertices, numVertices());
Arrays.sort(points, Point.XY_ORDER);
int n = points.length;
int k = 0;
Point[] res = new Point[2 * n];
for (int i = 0; i < n; i++) {
while (k >= 2 && ccw(res[k - 2], res[k - 1], points[i]) != COUNTER_CLOCKWISE) {
k--;
}
res[k] = points[i];
k++;
}
int t = k + 1;
for (int i = n - 2; i >= 0; i--) {
while (k >= t && ccw(res[k - 2], res[k - 1], points[i]) != COUNTER_CLOCKWISE) {
k--;
}
res[k] = points[i];
k++;
}
return new Polygon(Arrays.copyOf(res, k - 1));
}
int numVertices() {
return vertices.length;
}
double area() {
int n = numVertices();
double area = 0;
for (int i = 0; i < n; i++) {
area += vertices[i].cross(vertices[(i + 1) % n]);
}
return area / 2;
}
boolean isConvex() {
int n = numVertices();
boolean convex = true;
for (int i = 0; i < n; i++) {
Point prev = vertices[(i + n - 1) % n];
Point next = vertices[(i + 1) % n];
convex &= ccw(prev, vertices[i], next) != CLOCKWISE;
}
return convex;
}
int contains(Point p) {
int n = numVertices();
boolean in = false;
for (int i = 0; i < n; i++) {
Point a = vertices[i].subtract(p);
Point b = vertices[(i + 1) % n].subtract(p);
if (sign(a.cross(b)) == 0 && sign(a.dot(b)) <= 0) {
return ON;
}
if (compare(a.y, b.y) > 0) {
Point temp = a;
a = b;
b = temp;
}
if (sign(a.y) <= 0 && 0 < sign(b.y) && sign(a.cross(b)) > 0) {
in = !in;
}
}
return in ? IN : OUT;
}
@Override
public String toString() {
return Arrays.toString(vertices);
}
}
static int sign(double a) {
return a < -Main.eps ? -1 : a > Main.eps ? 1 : 0;
}
static int compare(double a, double b) {
return sign(a - b);
}
// 偏角ソート
static int compareArgument(long ax, long ay, long bx, long by) {
int orthantA = ay >= 0 ? ax >= 0 ? 0 : 1 : ax >= 0 ? 3 : 2;
int orthantB = by >= 0 ? bx >= 0 ? 0 : 1 : bx >= 0 ? 3 : 2;
if (orthantA == orthantB) {
return Long.compare(bx * ay, ax * by);
} else {
return Integer.compare(orthantA, orthantB);
}
}
static int compareArgument(double ax, double ay, double bx, double by) {
int orthantA = ay >= 0 ? ax >= 0 ? 0 : 1 : ax >= 0 ? 3 : 2;
int orthantB = by >= 0 ? bx >= 0 ? 0 : 1 : bx >= 0 ? 3 : 2;
if (orthantA == orthantB) {
return compare(bx * ay, ax * by);
} else {
return Integer.compare(orthantA, orthantB);
}
}
static int ccw(Point p0, Point p1, Point p2) {
Point a = p1.subtract(p0);
Point b = p2.subtract(p0);
int s = sign(a.cross(b));
if (s != 0) {
return s > 0 ? COUNTER_CLOCKWISE : CLOCKWISE;
} else if (sign(a.dot(b)) < 0) {
return BACK;
} else if (a.norm() < b.norm()) {
return FRONT;
} else {
return ON;
}
}
}
class FastIn extends In {
private final BufferedInputStream reader = new BufferedInputStream(System.in);
private final byte[] buffer = new byte[0x10000];
private int i = 0;
private int length = 0;
public int read() {
if (i == length) {
i = 0;
try {
length = reader.read(buffer);
} catch (IOException ignored) {
}
if (length == -1) {
return 0;
}
}
if (length <= i) {
throw new RuntimeException();
}
return buffer[i++];
}
String next() {
StringBuilder builder = new StringBuilder();
int b = read();
while (b < '!' || '~' < b) {
b = read();
}
while ('!' <= b && b <= '~') {
builder.appendCodePoint(b);
b = read();
}
return builder.toString();
}
String nextLine() {
StringBuilder builder = new StringBuilder();
int b = read();
while (b != 0 && b != '\r' && b != '\n') {
builder.appendCodePoint(b);
b = read();
}
if (b == '\r') {
read();
}
return builder.toString();
}
int nextInt() {
long val = nextLong();
if ((int)val != val) {
throw new NumberFormatException();
}
return (int)val;
}
long nextLong() {
int b = read();
while (b < '!' || '~' < b) {
b = read();
}
boolean neg = false;
if (b == '-') {
neg = true;
b = read();
}
long n = 0;
int c = 0;
while ('0' <= b && b <= '9') {
n = n * 10 + b - '0';
b = read();
c++;
}
if (c == 0 || c >= 2 && n == 0) {
throw new NumberFormatException();
}
return neg ? -n : n;
}
}
class In {
private final BufferedReader reader = new BufferedReader(new InputStreamReader(System.in), 0x10000);
private StringTokenizer tokenizer;
String next() {
try {
while (tokenizer == null || !tokenizer.hasMoreTokens()) {
tokenizer = new StringTokenizer(reader.readLine());
}
} catch (IOException ignored) {
}
return tokenizer.nextToken();
}
int nextInt() {
return Integer.parseInt(next());
}
long nextLong() {
return Long.parseLong(next());
}
double nextDouble() {
return Double.parseDouble(next());
}
char[] nextCharArray() {
return next().toCharArray();
}
String[] nextStringArray(int n) {
String[] s = new String[n];
for (int i = 0; i < n; i++) {
s[i] = next();
}
return s;
}
char[][] nextCharGrid(int n, int m) {
char[][] a = new char[n][m];
for (int i = 0; i < n; i++) {
a[i] = next().toCharArray();
}
return a;
}
int[] nextIntArray(int n) {
int[] a = new int[n];
for (int i = 0; i < n; i++) {
a[i] = nextInt();
}
return a;
}
int[] nextIntArray(int n, IntUnaryOperator op) {
int[] a = new int[n];
for (int i = 0; i < n; i++) {
a[i] = op.applyAsInt(nextInt());
}
return a;
}
int[][] nextIntMatrix(int h, int w) {
int[][] a = new int[h][w];
for (int i = 0; i < h; i++) {
a[i] = nextIntArray(w);
}
return a;
}
long[] nextLongArray(int n) {
long[] a = new long[n];
for (int i = 0; i < n; i++) {
a[i] = nextLong();
}
return a;
}
long[] nextLongArray(int n, LongUnaryOperator op) {
long[] a = new long[n];
for (int i = 0; i < n; i++) {
a[i] = op.applyAsLong(nextLong());
}
return a;
}
long[][] nextLongMatrix(int h, int w) {
long[][] a = new long[h][w];
for (int i = 0; i < h; i++) {
a[i] = nextLongArray(w);
}
return a;
}
List<List<Integer>> nextEdges(int n, int m, boolean directed) {
List<List<Integer>> res = new ArrayList<>();
for (int i = 0; i < n; i++) {
res.add(new ArrayList<>());
}
for (int i = 0; i < m; i++) {
int u = nextInt() - 1;
int v = nextInt() - 1;
res.get(u).add(v);
if (!directed) {
res.get(v).add(u);
}
}
return res;
}
}
class Out {
private final PrintWriter out = new PrintWriter(System.out);
private final PrintWriter err = new PrintWriter(System.err);
boolean autoFlush = false;
boolean enableDebug;
Out(boolean enableDebug) {
this.enableDebug = enableDebug;
}
void println(Object... args) {
if (args == null || args.getClass() != Object[].class) {
args = new Object[] {args};
}
out.println(Arrays.stream(args).map(obj -> {
Class<?> clazz = obj == null ? null : obj.getClass();
return clazz == Double.class ? String.format("%.10f", obj) :
clazz == byte[].class ? Arrays.toString((byte[])obj) :
clazz == short[].class ? Arrays.toString((short[])obj) :
clazz == int[].class ? Arrays.toString((int[])obj) :
clazz == long[].class ? Arrays.toString((long[])obj) :
clazz == char[].class ? Arrays.toString((char[])obj) :
clazz == float[].class ? Arrays.toString((float[])obj) :
clazz == double[].class ? Arrays.toString((double[])obj) :
clazz == boolean[].class ? Arrays.toString((boolean[])obj) :
obj instanceof Object[] ? Arrays.deepToString((Object[])obj) :
String.valueOf(obj);
}).collect(Collectors.joining(" ")));
if (autoFlush) {
out.flush();
}
}
void debug(Object... args) {
if (!enableDebug) {
return;
}
if (args == null || args.getClass() != Object[].class) {
args = new Object[] {args};
}
err.println(Arrays.stream(args).map(obj -> {
Class<?> clazz = obj == null ? null : obj.getClass();
return clazz == Double.class ? String.format("%.10f", obj) :
clazz == byte[].class ? Arrays.toString((byte[])obj) :
clazz == short[].class ? Arrays.toString((short[])obj) :
clazz == int[].class ? Arrays.toString((int[])obj) :
clazz == long[].class ? Arrays.toString((long[])obj) :
clazz == char[].class ? Arrays.toString((char[])obj) :
clazz == float[].class ? Arrays.toString((float[])obj) :
clazz == double[].class ? Arrays.toString((double[])obj) :
clazz == boolean[].class ? Arrays.toString((boolean[])obj) :
obj instanceof Object[] ? Arrays.deepToString((Object[])obj) :
String.valueOf(obj);
}).collect(Collectors.joining(" ")));
err.flush();
}
void println(char[] s) {
out.println(String.valueOf(s));
if (autoFlush) {
out.flush();
}
}
void println(int[] a) {
StringJoiner joiner = new StringJoiner(" ");
for (int i : a) {
joiner.add(Integer.toString(i));
}
out.println(joiner);
if (autoFlush) {
out.flush();
}
}
void println(long[] a) {
StringJoiner joiner = new StringJoiner(" ");
for (long i : a) {
joiner.add(Long.toString(i));
}
out.println(joiner);
if (autoFlush) {
out.flush();
}
}
void flush() {
err.flush();
out.flush();
}
}