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-9; 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 ans = 0; for (int i = 0; i < n; i++) { if (n < 100) { for (int j = 0; j < n; j++) { ans = Math.max(ans, x[i] * y[j] - y[i] * x[j]); } continue; } // x[i] * y[j] - y[i] * x[j] int l = 0; int r = p.length - 1; long lv = x[i] * ((long)p[l].y) - y[i] * ((long)p[l].x); long rv = x[i] * ((long)p[r].y) - y[i] * ((long)p[r].x); long max = 0; max = Math.max(max, lv); max = Math.max(max, rv); boolean bb = true; while (r - l > 100) { int lm = l + (r - l) / 3; int rm = r - (r - l) / 3; lv = x[i] * ((long)p[lm].y) - y[i] * ((long)p[lm].x); rv = x[i] * ((long)p[rm].y) - y[i] * ((long)p[rm].x); 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++) { long val = x[i] * ((long)p[j].y) - y[i] * ((long)p[j].x); max = Math.max(max, val); } } ans = Math.max(ans, max); } out.println(ans); } long check(int i, int l, int r) { long lv = x[i] * ((long)p[l].y) - y[i] * ((long)p[l].x); long rv = x[i] * ((long)p[r].y) - y[i] * ((long)p[r].x); 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 = x[i] * ((long)p[lm].y) - y[i] * ((long)p[lm].x); rv = x[i] * ((long)p[rm].y) - y[i] * ((long)p[rm].x); 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++) { long val = x[i] * ((long)p[j].y) - y[i] * ((long)p[j].x); max = Math.max(max, val); } 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 XY_ORDER = (a, b) -> compare(a.x, b.x) == 0 ? compare(a.y, b.y) : compare(a.x, b.x); static final Comparator YX_ORDER = (a, b) -> compare(a.y, b.y) == 0 ? compare(a.x, b.x) : compare(a.y, b.y); static final Comparator 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 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]) == 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]) == 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> nextEdges(int n, int m, boolean directed) { List> 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(); } }