package main
import (
"bufio"
"fmt"
"math"
"os"
"sort"
)
type Point struct {
X, Y float64
}
type Edge struct {
MinTheta, MaxTheta float64
X1, Y1, X2, Y2 float64
}
type WarehouseInterval struct {
MinTheta, MaxTheta float64
FrontEdges []Edge
BackEdges []Edge
}
func evalDistance(W *WarehouseInterval, theta float64) float64 {
for _, e := range W.FrontEdges {
if theta >= e.MinTheta-1e-9 && theta <= e.MaxTheta+1e-9 {
num := e.X1*e.Y2 - e.X2*e.Y1
den := math.Cos(theta)*(e.Y2-e.Y1) - math.Sin(theta)*(e.X2-e.X1)
if math.Abs(den) < 1e-12 {
return math.Inf(1)
}
return math.Abs(num / den)
}
}
return math.Inf(1)
}
func intersect(e Edge, theta float64) Point {
num := e.X1*e.Y2 - e.X2*e.Y1
den := math.Cos(theta)*(e.Y2-e.Y1) - math.Sin(theta)*(e.X2-e.X1)
if math.Abs(den) < 1e-12 {
return Point{0, 0}
}
t := math.Abs(num / den)
return Point{t * math.Cos(theta), t * math.Sin(theta)}
}
func evalArea(W *WarehouseInterval, theta1, theta2 float64) float64 {
mid := (theta1 + theta2) / 2.0
var front, back Edge
foundFront, foundBack := false, false
for _, e := range W.FrontEdges {
if mid >= e.MinTheta-1e-9 && mid <= e.MaxTheta+1e-9 {
front = e
foundFront = true
break
}
}
for _, e := range W.BackEdges {
if mid >= e.MinTheta-1e-9 && mid <= e.MaxTheta+1e-9 {
back = e
foundBack = true
break
}
}
if !foundFront || !foundBack {
return 0.0
}
AFront := intersect(front, theta1)
BFront := intersect(front, theta2)
areaFront := 0.5 * math.Abs(AFront.X*BFront.Y-AFront.Y*BFront.X)
ABack := intersect(back, theta1)
BBack := intersect(back, theta2)
areaBack := 0.5 * math.Abs(ABack.X*BBack.Y-ABack.Y*BBack.X)
return math.Max(0.0, areaBack-areaFront)
}
var tree []*WarehouseInterval
func insert(u, nodeL, nodeR, L, R int, W *WarehouseInterval, basicAngles []float64) {
if L <= nodeL && nodeR <= R {
if tree[u] == nil {
tree[u] = W
return
}
midTheta := (basicAngles[nodeL] + basicAngles[nodeR]) / 2.0
distW := evalDistance(W, midTheta)
distU := evalDistance(tree[u], midTheta)
if distW < distU {
tree[u] = W
}
return
}
mid := (nodeL + nodeR) / 2
if L < mid {
insert(2*u, nodeL, mid, L, R, W, basicAngles)
}
if R > mid {
insert(2*u+1, mid, nodeR, L, R, W, basicAngles)
}
}
func findIndex(arr []float64, val float64) int {
return sort.Search(len(arr), func(i int) bool {
return arr[i] >= val-1e-7
})
}
func main() {
reader := bufio.NewReader(os.Stdin)
var N int
if _, err := fmt.Fscan(reader, &N); err != nil {
return
}
var intervals []*WarehouseInterval
var rawAngles []float64
rawAngles = append(rawAngles, -math.Pi, math.Pi)
for i := 0; i < N; i++ {
var c int
fmt.Fscan(reader, &c)
vertices := make([]Point, c)
for j := 0; j < c; j++ {
fmt.Fscan(reader, &vertices[j].X, &vertices[j].Y)
}
area := 0.0
for j := 0; j < c; j++ {
p1 := vertices[j]
p2 := vertices[(j+1)%c]
area += p1.X*p2.Y - p2.X*p1.Y
}
if area < 0 {
for j, k := 0, c-1; j < k; j, k = j+1, k-1 {
vertices[j], vertices[k] = vertices[k], vertices[j]
}
}
angles := make([]float64, c+1)
angles[0] = math.Atan2(vertices[0].Y, vertices[0].X)
for j := 1; j <= c; j++ {
v := vertices[j%c]
a := math.Atan2(v.Y, v.X)
for a-angles[j-1] > math.Pi {
a -= 2 * math.Pi
}
for a-angles[j-1] < -math.Pi {
a += 2 * math.Pi
}
angles[j] = a
}
minA, maxA := angles[0], angles[0]
for j := 0; j < c; j++ {
if angles[j] < minA {
minA = angles[j]
}
if angles[j] > maxA {
maxA = angles[j]
}
}
var frontEdges, backEdges []Edge
for j := 0; j < c; j++ {
A := angles[j]
B := angles[j+1]
if math.Abs(A-B) < 1e-9 {
continue
}
e := Edge{X1: vertices[j].X, Y1: vertices[j].Y, X2: vertices[(j+1)%c].X, Y2: vertices[(j+1)%c].Y}
if A > B {
e.MinTheta = B
e.MaxTheta = A
frontEdges = append(frontEdges, e)
} else {
e.MinTheta = A
e.MaxTheta = B
backEdges = append(backEdges, e)
}
}
shift := 0.0
for minA+shift >= math.Pi {
shift -= 2 * math.Pi
}
for minA+shift < -math.Pi {
shift += 2 * math.Pi
}
minA += shift
maxA += shift
var W1Front, W1Back, W2Front, W2Back []Edge
processEdge := func(e Edge, isFront bool) {
s := e.MinTheta + shift
end := e.MaxTheta + shift
add := func(minT, maxT float64, w int) {
newE := Edge{MinTheta: minT, MaxTheta: maxT, X1: e.X1, Y1: e.Y1, X2: e.X2, Y2: e.Y2}
rawAngles = append(rawAngles, minT, maxT)
if w == 1 {
if isFront {
W1Front = append(W1Front, newE)
} else {
W1Back = append(W1Back, newE)
}
} else {
if isFront {
W2Front = append(W2Front, newE)
} else {
W2Back = append(W2Back, newE)
}
}
}
if end <= math.Pi {
add(s, end, 1)
} else if s >= math.Pi {
add(s-2*math.Pi, end-2*math.Pi, 2)
} else {
add(s, math.Pi, 1)
add(-math.Pi, end-2*math.Pi, 2)
}
}
for _, e := range frontEdges {
processEdge(e, true)
}
for _, e := range backEdges {
processEdge(e, false)
}
if len(W1Front) > 0 {
intervals = append(intervals, &WarehouseInterval{MinTheta: minA, MaxTheta: math.Min(maxA, math.Pi), FrontEdges: W1Front, BackEdges: W1Back})
}
if maxA > math.Pi && len(W2Front) > 0 {
intervals = append(intervals, &WarehouseInterval{MinTheta: -math.Pi, MaxTheta: maxA - 2*math.Pi, FrontEdges: W2Front, BackEdges: W2Back})
}
}
sort.Float64s(rawAngles)
var basicAngles []float64
for _, a := range rawAngles {
if len(basicAngles) == 0 || a-basicAngles[len(basicAngles)-1] > 1e-7 {
basicAngles = append(basicAngles, a)
}
}
M := len(basicAngles) - 1
tree = make([]*WarehouseInterval, 4*M+1)
for _, W := range intervals {
L := findIndex(basicAngles, W.MinTheta)
R := findIndex(basicAngles, W.MaxTheta)
if L < R {
insert(1, 0, M, L, R, W, basicAngles)
}
}
totalArea := 0.0
for i := 0; i < M; i++ {
t1, t2 := basicAngles[i], basicAngles[i+1]
if t2-t1 < 1e-9 {
continue
}
midTheta := (t1 + t2) / 2.0
u := 1
nodeL, nodeR := 0, M
var closest *WarehouseInterval
minDist := math.Inf(1)
for {
if tree[u] != nil {
d := evalDistance(tree[u], midTheta)
if d < minDist {
minDist = d
closest = tree[u]
}
}
if nodeL+1 == nodeR {
break
}
mid := (nodeL + nodeR) / 2
if i < mid {
u = 2 * u
nodeR = mid
} else {
u = 2*u + 1
nodeL = mid
}
}
if closest != nil {
totalArea += evalArea(closest, t1, t2)
}
}
fmt.Printf("%.10f\n", totalArea)
}