/** * Enclosure Area: Steven Zeil */ import java.awt.geom.Point2D; import java.io.BufferedReader; import java.io.FileNotFoundException; import java.io.FileReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.ArrayList; import java.util.Arrays; import java.util.Comparator; import java.util.Scanner; public class EnclosureArea_sjz { BufferedReader input; public EnclosureArea_sjz(BufferedReader input) { this.input = input; } public static void main(String[] args) throws FileNotFoundException, IOException { if (args.length > 0) { for (int i = 0; i < args.length; ++i) { try (BufferedReader input = new BufferedReader(new FileReader(args[i]))) { new EnclosureArea_sjz(input).solve(); } } } else { BufferedReader input = new BufferedReader (new InputStreamReader(System.in)); new EnclosureArea_sjz(input).solve(); } } java.awt.Point p0; class Point extends java.awt.Point implements Comparable { public Point (int x, int y) { super (x,y); } double angle; long area2; @Override public int compareTo(Point p) { long orient = orientation(this, p0, p); if (orient != 0L) { return (orient > 0L) ? 1 : -1; } else { return (p0.distanceSq(p) >= p0.distanceSq(this)) ? -1 : 1; } } } class PointsByAngle implements Comparator { @Override public int compare(Point p1, Point p2) { if (p1.angle < p2.angle) return -1; else if (p1.angle == p2.angle) return 0; else return 1; } } PointsByAngle compareByAngle = new PointsByAngle(); class Line { // ax + by + c = 0 public double a; public double b; public double c; public Line() { a = b = c = 0.0; } public Line (double aa, double bb, double cc) { this.a = aa; this.b = bb; this.c = cc; double r = Math.sqrt(a*a + b*b); a /= r; b /= r; c /= r; } public Line (Point p1, Point p2) { double dx = p2.x - p1.x; double dy = p2.y - p1.y; a = dy; b = -dx; c = (double)p1.y * dx - (double)p1.x * dy; double r = Math.sqrt(a*a + b*b); a /= r; b /= r; c /= r; } public Line (Point2D.Double p1, Point2D.Double p2) { double dx = p2.x - p1.x; double dy = p2.y - p1.y; a = dy; b = -dx; c = p1.y * dx - p1.x * dy; double r = Math.sqrt(a*a + b*b); a /= r; b /= r; c /= r; } public String toString() { return "" + a + "x + " + b + "y + " + c + "= 0"; } double y(double x) { if (b == 0.0) return Double.MAX_VALUE; else return (-c - a * x) / b; } double x(double y) { if (a == 0.0) return Double.MAX_VALUE; else return (-c - b * y) / a; } boolean isParallel (Line line2) { return (a == line2.a && b == line2.b) || (a == -line2.a && b == -line2.b); } Point2D.Double intersection (Line line2) { if (a == 0.0) { double y = -c / b; return new Point2D.Double(line2.x(y), y); } if (b == 0.0) { double x = -c / a; return new Point2D.Double(x, line2.y(x)); } if (line2.a == 0.0) { double y = -line2.c / line2.b; return new Point2D.Double(x(y), y); } if (line2.b == 0.0) { double x = -line2.c / line2.a; return new Point2D.Double(x, y(x)); } double m1 = -a / b; double c1 = -c / b; double m2 = -line2.a / line2.b; double c2 = -line2.c / line2.b; double x = (c2 - c1) / (m1 - m2); double y = (c1 * m2 - c2 * m1) / (m2 - m1); return new Point2D.Double(x, y); } Line parallel (double dist) { return new Line(a, b, c-dist); } double distance (Point2D.Double p) { return a * p.x + b * p.y + c; } } private long crossMult(Point p1, Point p2) { long x1 = p1.x; long y1 = p1.y; long x2 = p2.x; long y2 = p2.y; return Math.subtractExact(Math.multiplyExact(y2, x1), Math.multiplyExact(y1, x2)); } private void solve() { int N, K; Scanner in = new Scanner(input); N = in.nextInt(); K = in.nextInt(); Point[] hull = new Point[K]; for (int i = 0; i < K; ++i) { hull[i] = new Point(in.nextInt(), in.nextInt()); } int hullSize = convexHull(hull); /* for (int i = 0; i < hullSize; ++i) { System.err.println("" + i + " " + hull[i] + " " + + orientation(hull[i], hull[(i+1)%hullSize], hull[(i+2)%hullSize])); } */ // Associate with each point its angle about the center. double cx = 0.0; double cy = 0.0; for (int i = 0; i < hullSize; ++i) { cx += (double)hull[i].x; cy += (double)hull[i].y; } cx /= (double)hullSize; cy /= (double)hullSize; int minAnglePos = 0; Point[] tempA = new Point[hullSize]; for (int i = 0; i < hullSize; ++i) { hull[i].angle = Math.atan2(((double)hull[i].y) - cy, ((double)hull[i].x) - cx); if (hull[i].angle < hull[minAnglePos].angle) { minAnglePos = i; } tempA[i] = hull[i]; } //Arrays.sort(hull, 0, hullSize, compareByAngle); if (minAnglePos != 0) { for (int i = 0; i < hullSize; ++i) { hull[i] = tempA[(minAnglePos + i) % hullSize]; if (i > 0 && hull[i].angle < hull[i-1].angle) { System.err.println("*** Unstable problem set involving " + hull[i-1] + ": " + hull[i-1].angle + " and " + hull[i] + ": " + hull[i].angle); } } } long crossoverArea2 = crossMult(hull[hullSize-1], hull[0]); for (int i = 0; i < hullSize; ++i) { long dArea2 = 0L; long prior = 0L; if (i > 0) { prior = hull[i-1].area2; dArea2 = crossMult(hull[i-1], hull[i]); } hull[i].area2 = Math.addExact(prior, dArea2); //System.err.println("" + i + ": " + hull[i] + " Angle=" + hull[i].angle + " dArea=" + dArea2); } long baseArea2 = hull[hullSize-1].area2 + crossoverArea2; long maxArea2 = baseArea2; for (int i = K; i < N; ++i) { Point p = new Point(in.nextInt(), in.nextInt()); double pAngle = Math.atan2(((double)p.y) - cy, ((double)p.x) - cx); p.angle = pAngle; int position = Arrays.binarySearch(hull, 0, hullSize, p, compareByAngle); if (position < 0) { position = -(position+1); } position = position % hullSize; Line edge = new Line(hull[position], hull[(position+hullSize-1) % hullSize]); if (edge.distance(new Point2D.Double(p.x, p.y)) * edge.distance(new Point2D.Double(cx, cy)) < 0.0) { // Find the limiting point for adding to the hull at angle pAngle+90 double angle = pAngle + Math.PI/2.0; if (angle > Math.PI) { angle -= 2.0*Math.PI; } p.angle = angle; position = Arrays.binarySearch(hull, 0, hullSize, p, compareByAngle); if (position < 0) { position = -(position+1); } position = position % hullSize; int steps = 0; long orient1 = orientation(hull[position], p, hull[(position+1) % hullSize]); while (orient1 < 0) { position = (position + hullSize - 1) % hullSize; orient1 = orientation(hull[position], p, hull[(position+1) % hullSize]); ++steps; } while (orient1 >= 0) { position = (position + 1) % hullSize; orient1 = orientation(hull[position], p, hull[(position+1) % hullSize]); ++steps; } int stopPosition = position; // Find the limiting point for adding to the hull at angle pAngle-90 angle = pAngle - Math.PI/2.0; if (angle < -Math.PI) { angle += 2.0*Math.PI; } p.angle = angle; position = Arrays.binarySearch(hull, 0, hullSize, p, compareByAngle); if (position < 0) { position = -(position+1); } position = (position + 1) % hullSize; long orient = orientation(hull[position], p, hull[(position+1) % hullSize]); while (orient < 0) { position = (position + 1) % hullSize; orient = orientation(hull[position], p, hull[(position+1) % hullSize]); } while (orient > 0) { position = (position + hullSize - 1) % hullSize; orient = orientation(hull[position], p, hull[(position+1) % hullSize]); ++steps; } int startPosition = (position + 1) % hullSize;; long replacedArea2 = hull[stopPosition].area2 - hull[startPosition].area2; if (startPosition > stopPosition) { replacedArea2 = baseArea2 - hull[startPosition].area2 + hull[stopPosition].area2; } long c1 = crossMult(hull[stopPosition], p); long c2 = crossMult(hull[startPosition], p); long c2mc1 = c2 - c1; long replacedBy2 = c2 - c1 - replacedArea2; long candidateArea2 = baseArea2 + replacedBy2; long sum = 0; for (int j = startPosition; j < stopPosition; ++j) { int j1 = (j+1) % hullSize; sum = Math.addExact(sum, crossMult(hull[j], hull[j+1])); } sum = Math.addExact(sum, crossMult(hull[stopPosition], p)); sum = Math.addExact(sum, crossMult(p, hull[startPosition])); long candidateArea2a = Math.addExact(baseArea2, sum); if (candidateArea2 > maxArea2) { //System.err.println("Adding " + p); //System.err.println("Replacing hull points " + startPosition + " ... " + stopPosition); } maxArea2 = Math.max(maxArea2, candidateArea2); } else { //System.err.println("Excluding interior pt " + p); } } long area1 = maxArea2 / 2L; String decimal = ((maxArea2 % 2L) == 0) ? ".0" : ".5"; System.out.println("" + area1 + decimal); in.close(); } private long orientation(java.awt.Point p1, java.awt.Point p2, java.awt.Point p3) { long x1 = p1.x; long y1 = p1.y; long x2 = p2.x; long y2 = p2.y; long x3 = p3.x; long y3 = p3.y; long d = Math.subtractExact( Math.multiplyExact(Math.subtractExact(x2, x1), Math.subtractExact(y3, y1)), Math.multiplyExact(Math.subtractExact(y2, y1), Math.subtractExact(x3, x1)) ); if (d == 0L) return 0L; else return (d < 0L) ? -1L : 1L; } private long orientation1(java.awt.Point p1, java.awt.Point p2, java.awt.Point p3) { double d = ((double)p2.x - (double)p1.x)*((double)p3.y - (double)p1.y) - ((double)p2.y - (double)p1.y)*((double)p3.x - (double)p1.x); if (d == 0.0) return 0L; else return (d < 0.0) ? -1L : 1L; } private int convexHull(Point[] points) { int lowest = 0; for (int i = 0; i < points.length; ++i) { Point p = points[i]; if (points[lowest].y > p.y || (points[lowest].y == p.y && points[lowest].x > p.x)) lowest = i; } Point temp = points[0]; points[0] = points[lowest]; points[lowest] = temp; p0 = new java.awt.Point(points[0].x, points[0].y); Arrays.sort(points, 1, points.length); ArrayList hull = new ArrayList<>(); hull.add (points[0]); hull.add (points[1]); hull.add (points[2]); for (int i = 3; i < points.length; ++i) { Point p = points[i]; while (orientation(hull.get(hull.size()-2), hull.get(hull.size()-1), p) <= 0) { hull.remove(hull.size()-1); } hull.add(p); } for (int i = 0; i < hull.size(); ++i) { points[i] = hull.get(i); } return hull.size(); } }