結果
問題 | 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 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
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 |
ソースコード
package mainimport ("bufio""fmt""math""math/cmplx""os""strconv")var sc = bufio.NewScanner(os.Stdin)func main() {sc.Split(bufio.ScanWords)var ps []complex128for 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, rpreturn 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-ac := real(ba)*imag(pa) - imag(ba)*real(pa)switch {case c > 0:return 1 // leftcase c < 0:return -1 // rightdefault:return 0 // on the line}}func nearestP(p, a, b complex128) complex128 {ab, ba, pa, pb := a-b, b-a, p-a, p-bif 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}