← Home
For problem statement at 0-999/600-699/680-689/682/problemE.txt this is a correct solution, but verifier at 0-999/600-699/680-689/682/verifierE.go ends with All tests passed can you fix the verifier? package main

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

type Point struct {
	x, y int64
}

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

func area(a, b, c Point) int64 {
	v := cross(a, b, c)
	if v < 0 {
		return -v
	}
	return v
}

func main() {
	reader := bufio.NewReader(os.Stdin)
	var n int
	var S int64
	fmt.Fscan(reader, &n, &S)

	pts := make([]Point, n)
	for i := 0; i < n; i++ {
		fmt.Fscan(reader, &pts[i].x, &pts[i].y)
	}

	sort.Slice(pts, func(i, j int) bool {
		if pts[i].x != pts[j].x {
			return pts[i].x < pts[j].x
		}
		return pts[i].y < pts[j].y
	})

	var lower, upper []Point
	for _, p := range pts {
		for len(lower) >= 2 && cross(lower[len(lower)-2], lower[len(lower)-1], p) <= 0 {
			lower = lower[:len(lower)-1]
		}
		lower = append(lower, p)
	}
	for i := n - 1; i >= 0; i-- {
		p := pts[i]
		for len(upper) >= 2 && cross(upper[len(upper)-2], upper[len(upper)-1], p) <= 0 {
			upper = upper[:len(upper)-1]
		}
		upper = append(upper, p)
	}

	var hull []Point
	if len(lower) > 0 {
		hull = append(hull, lower[:len(lower)-1]...)
	}
	if len(upper) > 0 {
		hull = append(hull, upper[:len(upper)-1]...)
	}

	m := len(hull)
	var bestA, bestB, bestC Point
	maxArea := int64(-1)

	if m < 3 {
		bestA, bestB, bestC = pts[0], pts[1], pts[2]
	} else if m == 3 {
		bestA, bestB, bestC = hull[0], hull[1], hull[2]
	} else {
		for i := 0; i < m; i++ {
			k := (i + 2) % m
			for j := i + 1; j < m; j++ {
				for {
					nk := (k + 1) % m
					if nk == i {
						break
					}
					if area(hull[i], hull[j], hull[nk]) >= area(hull[i], hull[j], hull[k]) {
						k = nk
					} else {
						break
					}
				}
				a := area(hull[i], hull[j], hull[k])
				if a > maxArea {
					maxArea = a
					bestA = hull[i]
					bestB = hull[j]
					bestC = hull[k]
				}
			}
		}
	}

	ansA := Point{bestA.x + bestB.x - bestC.x, bestA.y + bestB.y - bestC.y}
	ansB := Point{bestB.x + bestC.x - bestA.x, bestB.y + bestC.y - bestA.y}
	ansC := Point{bestC.x + bestA.x - bestB.x, bestC.y + bestA.y - bestB.y}

	fmt.Printf("%d %d\n", ansA.x, ansA.y)
	fmt.Printf("%d %d\n", ansB.x, ansB.y)
	fmt.Printf("%d %d\n", ansC.x, ansC.y)
}