import java.io.*; import java.util.*; import java.util.function.BiFunction; public class JimmyDivideAndConquer { public static class Kattio extends PrintWriter { public Kattio(InputStream i) { super(new BufferedOutputStream(System.out)); r = new BufferedReader(new InputStreamReader(i)); } public Kattio(InputStream i, OutputStream o) { super(new BufferedOutputStream(o)); r = new BufferedReader(new InputStreamReader(i)); } public boolean hasMoreTokens() { return peekToken() != null; } public int getInt() { return Integer.parseInt(nextToken()); } public double getDouble() { return Double.parseDouble(nextToken()); } public long getLong() { return Long.parseLong(nextToken()); } public String getWord() { return nextToken(); } private BufferedReader r; private String line; private StringTokenizer st; private String token; private String peekToken() { if (token == null) try { while (st == null || !st.hasMoreTokens()) { line = r.readLine(); if (line == null) return null; st = new StringTokenizer(line); } token = st.nextToken(); } catch (IOException e) { } return token; } private String nextToken() { String ans = peekToken(); token = null; return ans; } } public static double EPS = 1e-9; public static boolean almostZero(double x) { return Math.abs(x) < EPS; } private static class PointD { public double x, y; public PointD() { this(0.0, 0.0); } public PointD(double x, double y) { this.x = x; this.y = y; } public boolean equals(Object object) { if (this == object) return true; if (object == null || getClass() != object.getClass()) return false; if (!super.equals(object)) return false; PointD other = (PointD) object; return almostZero(this.x - other.x) && almostZero(this.y - other.y); } public static PointD add(PointD p1, PointD p2) { return new PointD(p1.x + p2.x, p1.y + p2.y); } public static PointD sub(PointD p1, PointD p2) { return new PointD(p1.x - p2.x, p1.y - p2.y); } public static PointD mul(PointD p1, double scalar) { return new PointD(p1.x * scalar, p1.y * scalar); } public static PointD div(PointD p1, double scalar) { return new PointD(p1.x / scalar, p1.y / scalar); } public static double det(PointD a, PointD b) { return a.x * b.y - a.y * b.x; } } private static class LineD { public PointD a, b; public LineD(PointD a, PointD b) { this.a = a; this.b = b; } public LineD(double x1, double y1, double x2, double y2) { this(new PointD(x1, y1), new PointD(x2, y2)); } public static boolean intersect(LineD a, LineD b, PointD res) { PointD difv = PointD.sub(b.a, a.a), av = PointD.sub(a.b, a.a), bv = PointD.sub(b.a, b.b); double d = PointD.det(av, bv), fa = PointD.det(difv, bv), fb = PointD.det(av, difv); if (almostZero(d)) return false; if (d < 0) { d = -d; fa = -fa; fb = -fb; } PointD t = PointD.add(a.a, PointD.div(PointD.mul(av, fa), d)); if (res != null) { res.x = t.x; res.y = t.y; } return true; } } public static List mergeHulls(List hullA, List hullB, BiFunction minMax) { // There will be no vertical lines in hullA or hullB // Both hulls will go strictly from left to right, and start and end at the same x-coordinate int a = 0, b = 0; ArrayList result = new ArrayList<>(); PointD curA = hullA.get(a++), nextA = hullA.get(a++); PointD curB = hullB.get(b++), nextB = hullB.get(b++); assert curA.x == curB.x; double lastX = curA.x; result.add(new PointD(curA.x, minMax.apply(curA.y, curB.y))); while (true) { LineD lineA = new LineD(curA, nextA); LineD lineB = new LineD(curB, nextB); double nextX = Math.min(nextA.x, nextB.x); PointD res = new PointD(); if (LineD.intersect(lineA, lineB, res)) { if (res.x > lastX && res.x < nextX) { result.add(res); } } lastX = nextX; if (nextA.x == nextX) { double by = curB.y + (nextX - curB.x) * (nextB.y - curB.y) / (nextB.x - curB.x); PointD np = new PointD(nextX, minMax.apply(nextA.y, by)); result.add(np); if (a >= hullA.size()) break; curA = nextA; nextA = hullA.get(a++); } if (nextB.x == nextX) { double ay = curA.y + (nextX - curA.x) * (nextA.y - curA.y) / (nextA.x - curA.x); PointD np = new PointD(nextX, minMax.apply(ay, nextB.y)); result.add(np); if (b >= hullB.size()) break; curB = nextB; nextB = hullB.get(b++); } } return result; } public static List mergeMultipleHulls(List> hulls, int start, int end, BiFunction minMax) { if (start + 1 == end) { return hulls.get(start); } int mid = (start + end) / 2; List left = mergeMultipleHulls(hulls, start, mid, minMax); List right = mergeMultipleHulls(hulls, mid, end, minMax); return mergeHulls(left, right, minMax); } public static List joinHulls(List upperHull, List lowerHull) { // There will be no vertical lines in hullA or hullB // Both hulls will go strictly from left to right, and start and end at the same x-coordinate int a = 0, b = 0; ArrayList newUpper = new ArrayList<>(); ArrayList newLower = new ArrayList<>(); PointD curA = upperHull.get(a++), nextA = upperHull.get(a++); PointD curB = lowerHull.get(b++), nextB = lowerHull.get(b++); assert curA.x == curB.x; double lastX = curA.x; if (curA.y >= curB.y) { newUpper.add(curA); newLower.add(curB); } while (true) { LineD lineA = new LineD(curA, nextA); LineD lineB = new LineD(curB, nextB); double nextX = Math.min(nextA.x, nextB.x); PointD res = new PointD(); if (LineD.intersect(lineA, lineB, res)) { if (res.x > lastX - EPS && res.x < nextX + EPS) { newUpper.add(res); newLower.add(res); } } double ay = nextA.x == nextX ? nextA.y : curA.y + (nextX - curA.x) * (nextA.y - curA.y) / (nextA.x - curA.x); double by = nextB.x == nextX ? nextB.y : curB.y + (nextX - curB.x) * (nextB.y - curB.y) / (nextB.x - curB.x); if (ay >= by) { newUpper.add(new PointD(nextX, ay)); newLower.add(new PointD(nextX, by)); } lastX = nextX; if (nextA.x == nextX) { if (a >= upperHull.size()) { break; } curA = nextA; nextA = upperHull.get(a++); } if (nextB.x == nextX) { if (b >= lowerHull.size()) { break; } curB = nextB; nextB = lowerHull.get(b++); } } Collections.reverse(newLower); newUpper.addAll(newLower); return newUpper; } public static void main(String args[]) throws FileNotFoundException { Kattio io = new Kattio(System.in, System.out); // Kattio io = new Kattio(new FileInputStream("poly1.in"), System.out); // Kattio io = new Kattio(new FileInputStream("../../data/sample/3.in"), System.out); Locale.setDefault(Locale.ENGLISH); int n = io.getInt(); ArrayList points = new ArrayList<>(); double max = 0; for (int i = 0; i < n; i++) { PointD p = new PointD(io.getInt(), io.getInt()); max = Math.max(Math.max(max, p.x), p.y); points.add(p); } List upperLines = new ArrayList<>(), lowerLines = new ArrayList<>(); double left = 0, right = max; for (int i = 0; i < n; i++) { PointD p1 = points.get(i), p2 = points.get((i+1) % n); if (p1.x == p2.x) { if (p1.y < p2.y) { left = Math.max(left, p1.x); } else { right = Math.min(right, p1.x); } } else { if (p1.x < p2.x) { upperLines.add(new LineD(p1, p2)); } else { lowerLines.add(new LineD(p1, p2)); } } } if (left >= right) { io.println("0"); } else { List> upperHulls = new ArrayList<>(); List> lowerHulls = new ArrayList<>(); LineD leftBoundary = new LineD(left, 0, left, max); LineD rightBoundary = new LineD(right, 0, right, max); for (LineD upperLine : upperLines) { PointD lp = new PointD(), rp = new PointD(); LineD.intersect(leftBoundary, upperLine, lp); LineD.intersect(rightBoundary, upperLine, rp); upperHulls.add(Arrays.asList(lp, rp)); } for (LineD lowerLine : lowerLines) { PointD lp = new PointD(), rp = new PointD(); LineD.intersect(leftBoundary, lowerLine, lp); LineD.intersect(rightBoundary, lowerLine, rp); lowerHulls.add(Arrays.asList(lp, rp)); } List upperHull = mergeMultipleHulls(upperHulls, 0, upperHulls.size(), Math::min); List lowerHull = mergeMultipleHulls(lowerHulls, 0, lowerHulls.size(), Math::max); List polygon = joinHulls(upperHull, lowerHull); double area = 0; for (int i = 0; i < polygon.size(); i++) { area += PointD.det(polygon.get((i + 1) % polygon.size()), polygon.get(i)); } area /= 2.0; io.println(String.format("%.6f", area)); } io.close(); } }