結果

問題 No.199 星を描こう
コンテスト
ユーザー yukirin
提出日時 2016-04-11 16:06:52
言語 Go
(1.23.4)
結果
AC  
実行時間 2 ms / 2,000 ms
コード長 3,493 bytes
コンパイル時間 14,524 ms
コンパイル使用メモリ 218,844 KB
実行使用メモリ 5,248 KB
最終ジャッジ日時 2024-12-30 03:48:34
合計ジャッジ時間 15,609 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 25
権限があれば一括ダウンロードができます

ソースコード

diff # 

package main

import (
	"bufio"
	"fmt"
	"math"
	"math/cmplx"
	"os"
	"strconv"
)

var sc = bufio.NewScanner(os.Stdin)

func main() {
	sc.Split(bufio.ScanWords)
	var ps []complex128

	for i := 0; i < 5; i++ {
		ps = append(ps, complex(nextFloat(), nextFloat()))
	}

	if len(solve2(ps)) == 5 {
		fmt.Println("YES")
		return
	}
	fmt.Println("NO")
}

func nextLine() string {
	sc.Scan()
	return sc.Text()
}

func nextInt() int {
	i, _ := strconv.Atoi(nextLine())
	return i
}

func solve2(ps []complex128) []complex128 {
	lp, rp := leftMost(ps), rightMost(ps)
	ret := make([]complex128, 2, 500)
	ret[0], ret[1] = lp, rp
	return append(ret, solve(lp, rp, ps)...)
}

func solve(lp, rp complex128, ps []complex128) []complex128 {
	if len(ps) == 0 {
		return nil
	}

	a, b, c := equationL(lp, rp)
	updown, div := [][]complex128{make([]complex128, 0, 50), make([]complex128, 0, 50)}, make([]complex128, 2)
	maxU, maxD := float64(0), float64(0)
	ret := make([]complex128, 0, 100)

	for _, p := range ps {
		d := distance(a, b, c, p)
		switch side := posL(p, lp, rp); {
		case side > 0:
			if d > maxU {
				maxU, div[0] = d, p
			}
			updown[0] = append(updown[0], p)
		case side < 0:
			if d > maxD {
				maxD, div[1] = d, p
			}
			updown[1] = append(updown[1], p)
		}
	}

	if len(updown[0]) > 0 {
		ret = append(ret, div[0])
	}
	if len(updown[1]) > 0 {
		ret = append(ret, div[1])
	}

	left := [][]complex128{updown[0][:0], updown[1][:0]}
	right := [][]complex128{make([]complex128, 0, 25), make([]complex128, 0, 25)}
	tri := [][]complex128{[]complex128{lp, rp, div[0]}, []complex128{lp, rp, div[1]}}
	inter := []complex128{nearestP(div[0], lp, rp), nearestP(div[1], lp, rp)}
	for i := 0; i < 2; i++ {
		for _, p := range updown[i] {
			if inPolygon(p, tri[i]) {
				continue
			}
			if posL(p, inter[i], div[i]) > 0 {
				left[i] = append(left[i], p)
				continue
			}
			right[i] = append(right[i], p)
		}
	}

	ret = append(ret, solve(lp, div[0], left[0])...)
	ret = append(ret, solve(div[0], rp, right[0])...)
	ret = append(ret, solve(rp, div[1], left[1])...)
	ret = append(ret, solve(div[1], lp, right[1])...)
	return ret
}

func leftMost(ps []complex128) complex128 {
	p := ps[0]
	for _, v := range ps[1:] {
		if real(v) < real(p) {
			p = v
		}
	}
	return p
}

func rightMost(ps []complex128) complex128 {
	p := ps[0]
	for _, v := range ps[1:] {
		if real(v) > real(p) {
			p = v
		}
	}
	return p
}

func equationL(a, b complex128) (float64, float64, float64) {
	return imag(b) - imag(a), real(a) - real(b), imag(a)*real(b) - real(a)*imag(b)
}

func distance(a, b, c float64, z complex128) float64 {
	return math.Abs(a*real(z)+b*imag(z)+c) / math.Sqrt(a*a+b*b)
}

func posL(p, a, b complex128) int {
	ba, pa := b-a, p-a
	c := real(ba)*imag(pa) - imag(ba)*real(pa)
	switch {
	case c > 0:
		return 1 // left
	case c < 0:
		return -1 // right
	default:
		return 0 // on the line
	}
}

func nearestP(p, a, b complex128) complex128 {
	ab, ba, pa, pb := a-b, b-a, p-a, p-b
	if dot(ba, pa) < 0 {
		return a
	}

	if dot(ab, pb) < 0 {
		return b
	}
	return a + complex(dot(pa, ba)/(real(ba)*real(ba)+imag(ba)*imag(ba)), 0)*ba
}

func dot(a, b complex128) float64 {
	return real(a * cmplx.Conj(b))
}

func inPolygon(p complex128, ps []complex128) bool {
	ps = append(ps, ps[0])
	sign := posL(p, ps[0], ps[1])
	for i, v := range ps[1 : len(ps)-1] {
		if sign*posL(p, v, ps[i+2]) < 0 {
			return false
		}
	}
	return true
}

func nextFloat() float64 {
	f, _ := strconv.ParseFloat(nextLine(), 64)
	return f
}
0