← Home
For problem statement at 1000-1999/1300-1399/1380-1389/1381/problemE.txt this is a correct solution, but verifier at 1000-1999/1300-1399/1380-1389/1381/verifierE.go ends with All tests passed can you fix the verifier? package main

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

type Point struct {
	x, y int
}

type Edge struct {
	x1, y1, x2, y2 float64
}

type Event struct {
	x, dc2, dc1, dc0 float64
}

type QueryObj struct {
	f  float64
	id int
}

func main() {
	scanner := bufio.NewScanner(os.Stdin)
	scanner.Split(bufio.ScanWords)
	buf := make([]byte, 10*1024*1024)
	scanner.Buffer(buf, 10*1024*1024)

	scanInt := func() int {
		scanner.Scan()
		val, _ := strconv.Atoi(scanner.Text())
		return val
	}

	if !scanner.Scan() {
		return
	}
	n, _ := strconv.Atoi(scanner.Text())
	q := scanInt()

	pts := make([]Point, n)
	for i := 0; i < n; i++ {
		pts[i] = Point{scanInt(), scanInt()}
	}

	signedArea := 0.0
	for i := 0; i < n; i++ {
		j := (i + 1) % n
		signedArea += float64(pts[i].x*pts[j].y - pts[j].x*pts[i].y)
	}
	area := math.Abs(signedArea) / 2.0

	if signedArea < 0 {
		for i, j := 0, n-1; i < j; i, j = i+1, j-1 {
			pts[i], pts[j] = pts[j], pts[i]
		}
	}

	bot, top := 0, 0
	for i := 1; i < n; i++ {
		if pts[i].y < pts[bot].y {
			bot = i
		}
		if pts[i].y > pts[top].y {
			top = i
		}
	}

	var rightChain, leftChain []Edge

	curr := bot
	for curr != top {
		next := (curr + 1) % n
		rightChain = append(rightChain, Edge{
			float64(pts[curr].x), float64(pts[curr].y),
			float64(pts[next].x), float64(pts[next].y),
		})
		curr = next
	}

	curr = bot
	for curr != top {
		next := (curr - 1 + n) % n
		leftChain = append(leftChain, Edge{
			float64(pts[curr].x), float64(pts[curr].y),
			float64(pts[next].x), float64(pts[next].y),
		})
		curr = next
	}

	var Y []float64
	for _, p := range pts {
		Y = append(Y, float64(p.y))
	}
	sort.Float64s(Y)

	var uniqueY []float64
	for i, y := range Y {
		if i == 0 || y != Y[i-1] {
			uniqueY = append(uniqueY, y)
		}
	}

	var events []Event

	rIdx, lIdx := 0, 0

	getX := func(e Edge, y float64) float64 {
		if e.y1 == e.y2 {
			return e.x1
		}
		return e.x1 + (y-e.y1)*(e.x2-e.x1)/(e.y2-e.y1)
	}

	addSegment := func(x1, x2, yb, yt, W float64) {
		xmin, xmax := x1, x2
		if xmin > xmax {
			xmin, xmax = xmax, xmin
		}
		YLen := W * (yt - yb)
		if xmax == xmin {
			events = append(events, Event{x: xmin, dc2: 0, dc1: YLen, dc0: -YLen * xmin})
		} else {
			K := YLen / (xmax - xmin)
			events = append(events, Event{x: xmin, dc2: 0.5 * K, dc1: -K * xmin, dc0: 0.5 * K * xmin * xmin})
			events = append(events, Event{x: xmax, dc2: -0.5 * K, dc1: K*xmin + YLen, dc0: -0.5*K*xmin*xmin - YLen*(xmin+xmax)/2.0})
		}
	}

	for i := 0; i < len(uniqueY)-1; i++ {
		yb := uniqueY[i]
		yt := uniqueY[i+1]

		for rIdx < len(rightChain) && rightChain[rIdx].y2 <= yb {
			rIdx++
		}
		for lIdx < len(leftChain) && leftChain[lIdx].y2 <= yb {
			lIdx++
		}

		rEdge := rightChain[rIdx]
		lEdge := leftChain[lIdx]

		xRb := getX(rEdge, yb)
		xRt := getX(rEdge, yt)
		xLb := getX(lEdge, yb)
		xLt := getX(lEdge, yt)

		addSegment(xLb, xLt, yb, yt, 1)
		addSegment(xRb, xRt, yb, yt, 1)
		addSegment((xLb+xRb)/2.0, (xLt+xRt)/2.0, yb, yt, -2)
	}

	qObjs := make([]QueryObj, q)
	for i := 0; i < q; i++ {
		qObjs[i] = QueryObj{float64(scanInt()), i}
	}

	sort.Slice(events, func(i, j int) bool { return events[i].x < events[j].x })
	sort.Slice(qObjs, func(i, j int) bool { return qObjs[i].f < qObjs[j].f })

	ans := make([]float64, q)
	evIdx := 0
	c2, c1, c0 := 0.0, 0.0, 0.0

	for _, query := range qObjs {
		f := query.f
		for evIdx < len(events) && events[evIdx].x <= f+1e-9 {
			c2 += events[evIdx].dc2
			c1 += events[evIdx].dc1
			c0 += events[evIdx].dc0
			evIdx++
		}
		overlapArea := c2*f*f + c1*f + c0
		ans[query.id] = area - overlapArea
	}

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

	for i := 0; i < q; i++ {
		fmt.Fprintf(writer, "%.6f\n", ans[i])
	}
}