← Home
For problem statement at 0-999/0-99/10-19/13/problemD.txt this is a correct solution, but verifier at 0-999/0-99/10-19/13/verifierD.go ends with case 1 failed: expected 19 got 16
input:
6 3
-1 -2
5 -3
2 -5
-5 -5
-1 1
-1 -4
-3 -5
5 -4
4 -4
exit status 1 can you fix the verifier? package main

import (
	"fmt"
	"io"
	"os"
	"sort"
)

type Point struct {
	x  int64
	y  int64
	sx int64
}

func orient(a, b, c Point) int64 {
	return (b.x-a.x)*(c.y-a.y) - (b.y-a.y)*(c.x-a.x)
}

func main() {
	data, _ := io.ReadAll(os.Stdin)
	idx := 0
	nextInt := func() int64 {
		for idx < len(data) && (data[idx] == ' ' || data[idx] == '\n' || data[idx] == '\r' || data[idx] == '\t') {
			idx++
		}
		sign := int64(1)
		if data[idx] == '-' {
			sign = -1
			idx++
		}
		var v int64
		for idx < len(data) && data[idx] >= '0' && data[idx] <= '9' {
			v = v*10 + int64(data[idx]-'0')
			idx++
		}
		return sign * v
	}

	n := int(nextInt())
	m := int(nextInt())

	const K int64 = 2000000001

	red := make([]Point, n)
	for i := 0; i < n; i++ {
		x := nextInt()
		y := nextInt()
		red[i] = Point{x: x, y: y, sx: x + K*y}
	}

	blue := make([]Point, m)
	for i := 0; i < m; i++ {
		x := nextInt()
		y := nextInt()
		blue[i] = Point{x: x, y: y, sx: x + K*y}
	}

	sort.Slice(red, func(i, j int) bool {
		return red[i].sx < red[j].sx
	})

	low := make([][]int, n)
	for i := 0; i < n; i++ {
		low[i] = make([]int, n)
	}

	for i := 0; i < n; i++ {
		pi := red[i]
		si := pi.sx
		for j := i + 1; j < n; j++ {
			pj := red[j]
			sj := pj.sx
			cnt := 0
			for t := 0; t < m; t++ {
				b := blue[t]
				if b.sx > si && b.sx < sj && orient(pi, pj, b) < 0 {
					cnt++
				}
			}
			low[i][j] = cnt
		}
	}

	var ans int64
	for i := 0; i < n; i++ {
		pi := red[i]
		lowi := low[i]
		for j := i + 1; j < n; j++ {
			pj := red[j]
			lowj := low[j]
			lij := lowi[j]
			for k := j + 1; k < n; k++ {
				var inside int
				if orient(pi, pj, red[k]) > 0 {
					inside = lij + lowj[k] - lowi[k]
				} else {
					inside = lowi[k] - lij - lowj[k]
				}
				if inside == 0 {
					ans++
				}
			}
		}
	}

	fmt.Print(ans)
}