import java.io.*; import java.util.*; /** * Fairly simple solution that starts of with a rectangle and then * cuts out half planes one at a time. * Most of the code is just simple geometry primitives and Kattio. * * Time complexity: O(n^2) */ public class JimmySlowQuad { 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; } } private static final double EPS = 1e-9; public static double roundZero(double d) { return Math.abs(d) < EPS ? 0.0 : d; } 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; } static PointD add(PointD p1, PointD p2) { return new PointD(p1.x + p2.x, p1.y + p2.y); } static PointD sub(PointD p1, PointD p2) { return new PointD(p1.x - p2.x, p1.y - p2.y); } static PointD mul(PointD p1, double scalar) { return new PointD(p1.x * scalar, p1.y * scalar); } static PointD div(PointD p1, double scalar) { return new PointD(p1.x/scalar, p1.y/scalar); } static double det(PointD a, PointD b) { return a.x * b.y - a.y * b.x; } static double cross(PointD a, PointD b, PointD c) { return det(sub(b, a), sub(c, a)); } @Override public boolean equals(Object obj) { return x == ((PointD) obj).x && y == ((PointD) obj).y; } } private static class LineD { public PointD a, b; public LineD() { this(new PointD(), new PointD()); } public LineD(PointD a, PointD b) { this.a = a; this.b = b; } 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 = roundZero(PointD.det(av, bv)), fa = PointD.det(difv, bv), fb = PointD.det(av, difv); if (d == 0) 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; } @Override public String toString() { return String.format("(%f,%f)-(%f,%f)", a.x, a.y, b.x, b.y); } } private static class PolygonD { public List points; public PolygonD(Collection points) { this.points = new ArrayList<>(points); } double area() { double sum = 0; for (int i = 0; i < points.size(); i++) { sum += PointD.det(points.get(i), points.get((i + 1) % points.size())); } return Math.abs(sum / 2.0); } PolygonD cut(LineD line) { List res = new ArrayList<>(); for (int i = 0; i < this.points.size(); i++) { PointD cur = this.points.get(i), prev = i > 0 ? this.points.get(i-1) : this.points.get(this.points.size() - 1); boolean side = roundZero(PointD.cross(line.a, line.b, cur)) < 0; if (side != (roundZero(PointD.cross(line.a, line.b, prev)) < 0)) { PointD ipoint = new PointD(); boolean intersect = LineD.intersect(line, new LineD(cur, prev), ipoint); if (!intersect) { //System.out.println(String.format("wtf %s %s", line, new LineD(cur, prev))); } else { res.add(ipoint); } } if (side) res.add(cur); } return new PolygonD(res); } @Override public String toString() { StringBuilder sb = new StringBuilder(); for (PointD point : points) { sb.append(String.format("(%f %f) ", point.x, point.y)); } return sb.toString(); } } public static void main(String args[]) { Kattio io = new Kattio(System.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); } PolygonD current = new PolygonD(Arrays.asList( new PointD(0, 0), new PointD(0, max), new PointD(max, max), new PointD(max, 0) )); for (int i = 0; i < n; i++) { // io.println(current); LineD line = new LineD(points.get(i), points.get((i+1) % n)); // io.println("Cutting " + line); current = current.cut(line); //io.println(String.format("%.9f", current.area())); } //io.println(current); System.err.println("Poly size: " + current.points.size()); io.println(String.format("%.6f", current.area())); io.close(); } }