package main import ( "fmt" ) // GR is Golden Ratio const GR = 1.6180339887498948482045868343656 // GRSectionSearch returns z, for a minimum value of f(x) in [lb, ub], and the x. func GRSectionSearch(lb, ub int64, f func(int64) int64, n int) (z int64, x int64) { var x1, x2, f1, f2 int64 x1 = lb + int64(float64(ub-lb)/(GR+1)) x2 = lb + int64(float64(ub-lb)/GR) f1, f2 = f(x1), f(x2) for i := 0; i < n; i++ { if ub-lb < 4 { x, z = lb, f(lb) for j := lb + 1; j <= ub; j++ { if y := f(j); y < z { x, z = j, y } } return } if f1 <= f2 { ub = x2 x2, f2 = x1, f1 x1 = lb + int64(float64(ub-lb)/(GR+1)) f1 = f(x1) } else { lb = x1 x1, f1 = x2, f2 x2 = lb + int64(float64(ub-lb)/GR) f2 = f(x2) } } if f2 < f1 { x1, f1 = x2, f2 } return f1, x1 } const inf64 = 1 << 62 func min(x, y int64) int64 { if y < x { return y } return x } func max(x, y int64) int64 { if y > x { return y } return x } func main() { var N int var A, B [1010]int64 fmt.Scan(&N) for i := 0; i < N; i++ { fmt.Scan(&A[i], &B[i]) } f := func(x int64) int64 { var maxF, minF int64 minF, maxF = inf64, -1 for i := 0; i < N; i++ { g := A[i] + B[i]*int64(x) maxF = max(g, maxF) minF = min(g, minF) } return maxF - minF } z, x := GRSectionSearch(1, 1<<32, f, 50) lb := int64(1) for i := 0; i < 50; i++ { d := x - lb m := lb + d/2 if f(m) == z { x = m } else { lb = m + 1 } } fmt.Println(lb) }