import std.algorithm, std.conv, std.math, std.range, std.stdio, std.typecons; struct Vector { long x, y; this (long x, long y) { this.x = x; this.y = y; } Vector opBinary(string op)(Vector rhs) { static if (op == "+" || op == "-") mixin("return Vector(this.x"~op~"rhs.x, this.y"~op~"rhs.y);"); else static assert(0); } } long det(Vector v, Vector w) { return v.x * w.y - v.y * w.x; } struct Polygon { Vector[] points; this (Vector[] points ...) { assert (points.length >= 3); this.points = points; } ulong size() { return points.length; } // i-th vertex P_i Vector vertex(ulong i) { return points[i % $]; } // 0 : not a polygon // 1 : counterclockwise // -1 : clock wise private int _rotation = 2; int rotation() { if (_rotation != 2) return _rotation; // check if three successive points are on the same line foreach (i; 0 .. this.size()) { if (tri_sgn(vertex(i), vertex(i+1), vertex(i+2)) == 0) return _rotation = 0; } // check self-intersection foreach (i; 0 .. this.size()-2) foreach (j; i+2 .. this.size()) { if (intersect(vertex(i), vertex(i+1), vertex(j), vertex(j+1))) return _rotation = 0; } auto i = points.minIndex!((p, q) => p.x < q.x || (p.x == q.x && p.y < q.y)); return _rotation = tri_sgn(vertex(i-1), vertex(i), vertex(i+1)); } } // 0 : on the same line // 1 : counterclockwise // -1 : clockwise int tri_sgn(Vector a, Vector b, Vector c) { return cast(int) det(b-a, c-a).sgn; } // if the point p is between (allow to be the same point) the line segment ab bool between(Vector a, Vector p, Vector b) { return tri_sgn(a, p, b) == 0 && sgn(p.x - a.x) * sgn(p.x - b.x) <= 0 && sgn(p.y - a.y) * sgn(p.y - b.y) <= 0; } // determine whether line segments ab and cd intersect bool intersect(Vector a, Vector b, Vector c, Vector d) { if (between(a, c, b) || between(a, d, b) || between(c, a, d) || between(c, b, d)) return true; auto sign1 = tri_sgn(a, b, c) * tri_sgn(a, b, d); auto sign2 = tri_sgn(c, d, a) * tri_sgn(c, d, b); if (sign1 < 0 && sign2 < 0) return true; return false; } int solve(Polygon poly) { if (poly.rotation == 0) return 0; bool[ulong] visible; foreach (i; 0 .. poly.size) { visible[i] = true; } // counterclockwise auto r = poly.rotation > 0 ? iota(0uL, poly.size, 1) : iota(poly.size, 0uL, -1); foreach (i; r) { auto a = poly.vertex(i), b = poly.vertex(i+poly.rotation); foreach (j; 0 .. poly.size) { // j-th vertex is on the right hand side of the line segment ab if (visible[j] && tri_sgn(a, b, poly.vertex(j)) < 0) { visible[j] = false; } } } if (visible.values.reduce!"a || b") return 1; else return -1; } void main() { auto N = readln[0 .. $-1].to!ulong; Vector[] points; foreach (_; 0 .. N) { auto xy = readln.split.to!(long[]); points ~= Vector(xy[0], xy[1]); } auto poly = Polygon(points); solve(poly).writeln(); }