/** * Sort the points in clockwise order. Then extend out each edge to find * the intersection point if it exists. If it does not exist, then report * infinitely many. For consecutive edges A,B,C in the convex hull, edge * B and the extensions of A and C form a triangle. For this triangle, * iterate over all integer y coordinates occupied by the triangle. * Calculate the x coordinate range strictly inside the triangle for * each y coordinate. Add these values up for each triple of consecutive * edges. * Since the bound on x,y coordinates is |x|,|y|<=1000, each triangle can * cover a range of coordinates of size up to ~4 million. Calculating the * x coordinate range for each y coordinate is can be done in constant time. * Where N is the number of points and K is the bound on x,y coordinates, * this approach has complexity O(N*K^2). For N=50 and K=1000, this should * be feasible. * This implementation gets WRONG ANSWER because of integer overflow. * * @author Finn Lidbetter */ import java.util.Comparator import java.util.Arrays import java.util.HashSet fun main(args: Array) { val n = readLine()!!.toInt() var points = Array(n) { _ -> Point(0,0)} for (i in 0..n-1) { val tokens = readLine()!!.split(" ") points[i] = Point(tokens[0].toLong(), tokens[1].toLong()) } val convexHull = convexHull(points) // println(Arrays.toString(convexHull)) var infinite = false var extensionPts = 0L for (i in 0..n-1) { val line1 = Line(convexHull[i], convexHull[(i+1)%n]) val line2 = Line(convexHull[(i+3)%n], convexHull[(i+2)%n]) if (line1.cross(line2) >= 0L) { infinite = true break } val intersection = line1.intersection(line2)!! // println(intersection) extensionPts += countInteriorLatticePoints( convexHull[(i+1)%n], convexHull[(i+2)%n], intersection ) } if (infinite) { println("infinitely many") } else { println(extensionPts) } } fun countInteriorLatticePoints(p1: Point, p2: Point, p3: FracPoint): Long { val line12 = FracLine(FracPoint(p1), FracPoint(p2)) val line13 = FracLine(FracPoint(p1), p3) val line23 = FracLine(FracPoint(p2), p3) val yMinStrictVals = longArrayOf(line12.yMinStrict, line13.yMinStrict, line23.yMinStrict) val yMaxStrictVals = longArrayOf(line12.yMaxStrict, line13.yMaxStrict, line23.yMaxStrict) val yMinStrict = yMinStrictVals.min() val yMaxStrict = yMaxStrictVals.max() var total = 0L for (y in yMinStrict!!..yMaxStrict!!) { val xVals = arrayOf(line12.xAt(y), line13.xAt(y), line23.xAt(y)) // val xValsStr = Arrays.toString(xVals) // println("\t\ty: $y, xVals: $xValsStr") val xMin = xVals.nullMin()!!.strictCeil() val xMax = xVals.nullMax()!!.strictFloor() // println(String.format("\t\t\tline12: %s x=%s", line12, xVals[0])) // println(String.format("\t\t\tline13: %s, x=%s", line13, xVals[1])) // println(String.format("\t\t\tline23: %s, x=%s", line23, xVals[2])) // println("\t\ty: $y, xMin: $xMin, xMax: $xMax") if (xMax >= xMin) { total += xMax - xMin + 1 } } // println("\ttotal: $total") return total } fun Array.nullMin(): Fraction? { return this.reduce() { acc, element -> if (acc == null) element else { if (element==null) acc else { if (element < acc) element else acc } } } } fun Array.nullMax(): Fraction? { return this.reduce() { acc, element -> if (acc == null) element else { if (element==null) acc else { if (element > acc) element else acc } } } } fun convexHull(pts: Array): Array { val n = pts.size var k = 0 var count = 0 val arr: Array = arrayOfNulls(2 * n) Arrays.sort(pts, PointComparator()) for (i in 0 until n) { while (k >= 2 && cross(arr[k - 2]!!, arr[k - 1]!!, pts[i]) <= 0) { k-- } arr[k++] = pts[i] } run { var i = n - 2 val t = k + 1 while (i >= 0) { while (k >= t && cross(arr[k - 2]!!, arr[k - 1]!!, pts[i]) <= 0L) { k-- } arr[k++] = pts[i] i-- } } val pt_set: HashSet = HashSet() val hull: Array = Array(n){ _ -> Point(0,0)} for (i in 0 until k) if (!pt_set.contains(arr[i])) { hull[count++] = arr[i]!! pt_set.add(arr[i]!!) } return Arrays.copyOfRange(hull, 0, count) } class PointComparator : java.util.Comparator { override fun compare(p1: Point, p2: Point): Int { if (p1.x==p2.x) { if (p1.y == p2.y) { return 0 } else if (p1.y > p2.y) { return 1 } } else if (p1.x > p2.x) { return 1 } return -1 } } fun cross(a: Point, b: Point, c: Point): Long { return (b.x - a.x) * (c.y - a.y) - (b.y - a.y) * (c.x - a.x) } class Fraction(num: Long, denom: Long) { val num: Long val denom: Long init { if (denom < 0L) { this.num = -num this.denom = -denom } else { this.num = num this.denom = denom } } fun floor(): Long { var result = num / denom if (result * denom > num) { result -= 1 } return result } fun strictFloor(): Long { var result = floor() if (result*denom == num) { result -= 1 } return result } fun ceil(): Long { var result = num / denom if (result*denom < num) { result += 1 } return result } fun strictCeil(): Long { var result = ceil() if (result*denom == num) { result += 1 } return result } override fun equals(other: Any?): Boolean { other as Fraction return num*other.denom == denom*other.num } operator fun compareTo(f2: Fraction): Int { return (num*f2.denom).compareTo(f2.num*denom) } operator fun plus(f2: Fraction): Fraction { return Fraction( num * f2.denom + f2.num * denom, denom * f2.denom) } operator fun times(f2: Fraction): Fraction { return Fraction( num * f2.num, denom*f2.denom ) } operator fun unaryMinus() = Fraction(-num, denom) operator fun minus(f2: Fraction): Fraction { return this + (-f2) } operator fun div(f2: Fraction): Fraction { return Fraction(num * f2.denom, denom*f2.num) } fun reciprocal(): Fraction { return Fraction(denom, num) } override fun toString(): String { return "$num/$denom" } } data class Point(val x: Long, val y: Long) data class FracPoint(val x: Fraction, val y: Fraction) { constructor(x: Long, y: Long): this(Fraction(x, 1), Fraction(y, 1)) constructor(point: Point): this(Fraction(point.x, 1), Fraction(point.y, 1)) } data class Line(val p1: Point, val p2: Point) { fun cross(line2: Line): Long { val dx1 = p2.x - p1.x val dy1 = p2.y - p1.y val dx2 = line2.p2.x - line2.p1.x val dy2 = line2.p2.y - line2.p1.y return dx1*dy2 - dx2*dy1 } fun intersection(line2: Line): FracPoint? { val x1 = p1.x val y1 = p1.y val x2 = p2.x val y2 = p2.y val x3 = line2.p1.x val y3 = line2.p1.y val x4 = line2.p2.x val y4 = line2.p2.y var denom = (x1 - x2)*(y3-y4) - (y1-y2)*(x3-x4) if (denom == 0L) { return null } var pxn = (x1*y2 - y1*x2)*(x3-x4) - (x1-x2)*(x3*y4 - y3*x4) var pyn = (x1*y2 - y1*x2)*(y3-y4) - (y1-y2)*(x3*y4 - y3*x4) if (denom < 0L) { denom *= -1 pxn *= -1 pyn *= -1 } val px = Fraction(pxn, denom) val py = Fraction(pyn, denom) return FracPoint(px, py) } } class FracLine(p1: FracPoint, p2: FracPoint) { val p1: FracPoint val p2: FracPoint val yMinStrict: Long val yMaxStrict: Long val yMin: Long val yMax: Long val mInv: Fraction val bOverM: Fraction init { this.p1 = p1 this.p2 = p2 if (p1.y <= p2.y) { yMin = p1.y.ceil() yMinStrict = p1.y.strictCeil() yMax = p2.y.floor() yMaxStrict = p2.y.strictFloor() } else { yMin = p2.y.ceil() yMinStrict = p2.y.strictCeil() yMax = p1.y.floor() yMaxStrict = p1.y.strictFloor() } val m = (p2.y - p1.y) / (p2.x - p1.x) mInv = m.reciprocal() bOverM = p1.y * mInv - p1.x } fun xAt(y: Long): Fraction? { if (yyMax || p1.y==p2.y) { return null } return Fraction(bOverM.denom*y*mInv.num - bOverM.num * mInv.denom, mInv.denom*bOverM.denom) } override fun toString(): String { return String.format("%s--%s", this.p1, this.p2) } }