結果
| 問題 | No.2012 Largest Triangle |
| ユーザー |
 Yu_212
|
| 提出日時 | 2022-07-15 23:08:03 |
| 言語 | Java (openjdk 23) |
| 結果 |
AC
|
| 実行時間 | 909 ms / 2,500 ms |
| コード長 | 24,298 bytes |
| コンパイル時間 | 3,523 ms |
| コンパイル使用メモリ | 95,760 KB |
| 実行使用メモリ | 74,316 KB |
| 最終ジャッジ日時 | 2024-06-27 21:23:20 |
| 合計ジャッジ時間 | 22,496 ms |
|
ジャッジサーバーID （参考情報） |
judge3 / judge1 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 1 |
| other | AC * 41 |
ソースコード
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;}@Overridepublic 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);}@Overridepublic 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);}@Overridepublic 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());}@Overridepublic 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;}@Overridepublic 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();}}