For problem statement at 1000-1999/1200-1299/1210-1219/1218/problemB.txt this is a correct solution, but verifier at 1000-1999/1200-1299/1210-1219/1218/verifierB.go ends with Test 1 failed
Input:
2
4
10 10
13 10
13 11
10 11
4
20 20
22 20
22 21
20 21
Expected:
2.5000000000Got:
3.0000000000
exit status 1 can you fix the verifier? ```go
package main
import (
"bufio"
"fmt"
"math"
"os"
"sort"
"strconv"
)
type Point struct {
x, y float64
}
type Segment struct {
P, Q Point
start, end float64
id int
}
type Event struct {
Angle float64
Type int
Seg *Segment
}
func cross(P, Q Point) float64 {
return P.x*Q.y - P.y*Q.x
}
func getAngle(p Point) float64 {
a := math.Atan2(p.y, p.x)
if a < 0 {
a += 2 * math.Pi
}
return a
}
func dist(s *Segment, alpha float64) float64 {
num := s.P.x*s.Q.y - s.P.y*s.Q.x
den := math.Cos(alpha)*(s.Q.y-s.P.y) - math.Sin(alpha)*(s.Q.x-s.P.x)
if math.Abs(den) < 1e-12 {
return math.Inf(1)
}
d := num / den
if d < 0 {
return -d
}
return d
}
func less(a, b *Segment) bool {
start := math.Max(a.start, b.start)
end := math.Min(a.end, b.end)
phi := start + (end-start)/2.0
if end <= start {
phi = start
}
ta := dist(a, phi)
tb := dist(b, phi)
return ta < tb
}
func insert(active *[]*Segment, s *Segment) {
l, r := 0, len(*active)
for l < r {
m := (l + r) / 2
if less((*active)[m], s) {
l = m + 1
} else {
r = m
}
}
*active = append(*active, nil)
copy((*active)[l+1:], (*active)[l:])
(*active)[l] = s
}
func remove(active *[]*Segment, s *Segment) {
for i, seg := range *active {
if seg == s {
copy((*active)[i:], (*active)[i+1:])
*active = (*active)[:len(*active)-1]
break
}
}
}
func main() {
scanner := bufio.NewScanner(os.Stdin)
scanner.Split(bufio.ScanWords)
if !scanner.Scan() {
return
}
n, _ := strconv.Atoi(scanner.Text())
var events []Event
addSegment := func(P, Q Point, start, end float64, id int) {
seg := &Segment{P, Q, start, end, id}
events = append(events, Event{start, 1, seg})
events = append(events, Event{end, 0, seg})
}
for i := 0; i < n; i++ {
scanner.Scan()
c, _ := strconv.Atoi(scanner.Text())
pts := make([]Point, c)
for j := 0; j < c; j++ {
scanner.Scan()
x, _ := strconv.ParseFloat(scanner.Text(), 64)
scanner.Scan()
y, _ := strconv.ParseFloat(scanner.Text(), 64)
pts[j] = Point{x, y}
}
for j := 0; j < c; j++ {
P := pts[j]
Q := pts[(j+1)%c]
if math.Abs(cross(P, Q)) < 1e-9 {
continue
}
a1 := getAngle(P)
a2 := getAngle(Q)
if math.Abs(a1-a2) > math.Pi {
start1, end1 := math.Max(a1, a2), 2*math.Pi
start2, end2 := 0.0, math.Min(a1, a2)
if end1-start1 > 1e-11 {
addSegment(P, Q, start1, end1, i)
}
if end2-start2 > 1e-11 {
addSegment(P, Q, start2, end2, i)
}
} else {
start, end := math.Min(a1, a2), math.Max(a1, a2)
if end-start > 1e-11 {
addSegment(P, Q, start, end, i)
}
}
}
}
sort.Slice(events, func(i, j int) bool {
if math.Abs(events[i].Angle-events[j].Angle) > 1e-11 {
return events[i].Angle < events[j].Angle
}
return events[i].Type < events[j].Type
})
if len(events) == 0 {
fmt.Printf("%.10f\n", 0.0)
return
}
active := make([]*Segment, 0)
last_theta := events[0].Angle
totalArea := 0.0
for i := 0; i < len(events); i++ {
curr_theta := events[i].Angle
if curr_theta > last_theta+1e-11 {
if len(active) >= 2 {
s1 := active[0]
s2 := active[1]
if s1.id == s2.id {
d11 := dist(s1, last_theta)
d12 := dist(s1, curr_theta)
d21 := dist(s2, last_theta)
d22 := dist(s2, curr_theta)
da := 0.5 * math.Sin(curr_theta-last_theta) * (d21*d22 - d11*d12)
if da > 0 {
totalArea += da
}
}
}
last_theta = curr_theta
}
if events[i].Type == 0 {
remove(&active, events[i].Seg)
} else {
insert(&active, events[i].Seg)
}
}
fmt.Printf("%.10f\n", totalArea)
}
```