← Home
package main

import (
	"bufio"
	"fmt"
	"math"
	"os"
	"sort"
)

func main() {
	in := bufio.NewReader(os.Stdin)
	var n int
	if _, err := fmt.Fscan(in, &n); err != nil {
		return
	}

	l := make([]float64, n)
	r := make([]float64, n)
	ySet := make(map[float64]bool)

	for i := 0; i < n; i++ {
		var L, R float64
		fmt.Fscan(in, &L, &R)
		l[i] = L
		r[i] = R
		ySet[L] = true
		ySet[R] = true
	}

	var y []float64
	for v := range ySet {
		y = append(y, v)
	}
	sort.Float64s(y)

	nGL := 50
	xGL, wGL := getGaussLegendre(nGL)

	ans := make([][]float64, n)
	for i := range ans {
		ans[i] = make([]float64, n)
	}

	dp := make([]float64, n+1)
	dpi := make([]float64, n+1)
	P := make([]float64, n)
	A_buf := make([]int, 0, n)

	for s := 0; s < len(y)-1; s++ {
		W := y[s+1] - y[s]
		if W <= 0 {
			continue
		}

		A := A_buf[:0]
		c1 := 0
		for i := 0; i < n; i++ {
			if l[i] <= y[s] && r[i] >= y[s+1] {
				A = append(A, i)
			} else if r[i] <= y[s] {
				c1++
			}
		}

		if len(A) == 0 {
			continue
		}

		for k := 0; k < nGL; k++ {
			t_mapped := (W/2)*xGL[k] + (W/2)
			t_global := y[s] + t_mapped
			wt := wGL[k] * (W / 2)

			for i := 0; i <= len(A); i++ {
				dp[i] = 0
			}
			dp[0] = 1.0

			for idx, i := range A {
				p := (t_global - l[i]) / (r[i] - l[i])
				if p < 0 {
					p = 0
				}
				if p > 1 {
					p = 1
				}
				P[idx] = p
			}

			for idx := range A {
				p := P[idx]
				q := 1.0 - p
				for v := idx + 1; v >= 1; v-- {
					dp[v] = dp[v]*q + dp[v-1]*p
				}
				dp[0] = dp[0] * q
			}

			for idx, i := range A {
				p := P[idx]
				q := 1.0 - p
				if q > 0.5 {
					val := dp[0] / q
					if val < 0 { val = 0 }
					if val > 1 { val = 1 }
					dpi[0] = val
					for v := 1; v < len(A); v++ {
						val = (dp[v] - dpi[v-1]*p) / q
						if val < 0 { val = 0 }
						if val > 1 { val = 1 }
						dpi[v] = val
					}
				} else {
					val := dp[len(A)] / p
					if val < 0 { val = 0 }
					if val > 1 { val = 1 }
					dpi[len(A)-1] = val
					for v := len(A) - 2; v >= 0; v-- {
						val = (dp[v+1] - dpi[v+1]*q) / p
						if val < 0 { val = 0 }
						if val > 1 { val = 1 }
						dpi[v] = val
					}
				}

				factor := wt / (r[i] - l[i])
				for v := 0; v < len(A); v++ {
					ans[i][v+c1] += dpi[v] * factor
				}
			}
		}
	}

	out := bufio.NewWriter(os.Stdout)
	defer out.Flush()

	for i := 0; i < n; i++ {
		for j := 0; j < n; j++ {
			if j > 0 {
				fmt.Fprint(out, " ")
			}
			fmt.Fprintf(out, "%.9f", ans[i][j])
		}
		fmt.Fprintln(out)
	}
}

func getGaussLegendre(n int) ([]float64, []float64) {
	x := make([]float64, n)
	w := make([]float64, n)
	m := (n + 1) / 2
	for i := 0; i < m; i++ {
		z := math.Cos(math.Pi * (float64(i) + 0.75) / (float64(n) + 0.5))
		var pp float64
		for iter := 0; iter < 100; iter++ {
			p1 := 1.0
			p2 := 0.0
			for j := 0; j < n; j++ {
				p3 := p2
				p2 = p1
				p1 = ((2.0*float64(j)+1.0)*z*p2 - float64(j)*p3) / (float64(j) + 1.0)
			}
			pp = float64(n) * (z*p1 - p2) / (z*z - 1.0)
			z1 := z
			z = z1 - p1/pp
			if math.Abs(z-z1) < 1e-14 {
				break
			}
		}
		x[i] = -z
		x[n-1-i] = z
		w[i] = 2.0 / ((1.0 - z*z) * pp * pp)
		w[n-1-i] = w[i]
	}
	return x, w
}