結果

問題 No.199 星を描こう
ユーザー yukirinyukirin
提出日時 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
このコードへのチャレンジ
(要ログイン)

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
5,248 KB
testcase_01 AC 1 ms
5,248 KB
testcase_02 AC 1 ms
5,248 KB
testcase_03 AC 1 ms
5,248 KB
testcase_04 AC 1 ms
5,248 KB
testcase_05 AC 1 ms
5,248 KB
testcase_06 AC 1 ms
5,248 KB
testcase_07 AC 1 ms
5,248 KB
testcase_08 AC 1 ms
5,248 KB
testcase_09 AC 1 ms
5,248 KB
testcase_10 AC 1 ms
5,248 KB
testcase_11 AC 1 ms
5,248 KB
testcase_12 AC 2 ms
5,248 KB
testcase_13 AC 1 ms
5,248 KB
testcase_14 AC 1 ms
5,248 KB
testcase_15 AC 1 ms
5,248 KB
testcase_16 AC 1 ms
5,248 KB
testcase_17 AC 1 ms
5,248 KB
testcase_18 AC 1 ms
5,248 KB
testcase_19 AC 2 ms
5,248 KB
testcase_20 AC 1 ms
5,248 KB
testcase_21 AC 1 ms
5,248 KB
testcase_22 AC 1 ms
5,248 KB
testcase_23 AC 2 ms
5,248 KB
testcase_24 AC 1 ms
5,248 KB
testcase_25 AC 1 ms
5,248 KB
testcase_26 AC 2 ms
5,248 KB
testcase_27 AC 1 ms
5,248 KB
権限があれば一括ダウンロードができます

ソースコード

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
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0