結果

問題 No.5009 Draw A Convex Polygon
ユーザー urutom
提出日時 2022-12-12 01:47:27
言語 Go
(1.23.4)
結果
AC  
実行時間 955 ms / 2,600 ms
コード長 4,109 bytes
コンパイル時間 1,989 ms
実行使用メモリ 56,100 KB
スコア 1,000,000
平均クエリ数 1000001.00
最終ジャッジ日時 2022-12-12 01:47:32
合計ジャッジ時間 3,866 ms
ジャッジサーバーID
（参考情報） 		judge11 / judge14
純コード判定しない問題か言語
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 1
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

/*
https://yukicoder.me/problems/no/5009
This program aims to solve the above competitive programming problem
utilizing Farey sequence e.g. F_4=[0/1, 1/4, 1/3, 1/2, 2/3, 3/4, 1/1]
for more information, cf. https://en.wikipedia.org/wiki/Farey_sequence
*/
package main
import (
    "bufio"
    "fmt"
    "os"
    "sort"
)
var writer *bufio.Writer
const (
    N = 1_000_000 // upper limit number of points
    // the number the of 641-th Farey sequence enough to cover `N`/8
    // according to OEIS(A005728), see https://oeis.org/A005728
    Order = 641
)
// Farey fraction
type farey struct {
    a, b int // `a`/`b`, `b`!=0 and supposed to be coprime
}
// Farey sequence
type fareySeq []farey
// sum of all denominators in the sequence,
// will be used to determine where to begin an output sequence
func (fseq fareySeq) height() (ret int) {
    for _, f := range fseq {
        ret += f.b
    }
    return ret
}
// computes the greatest common divisor of a and b
func gcd(a, b int) int {
    if b == 0 {
        return a
    }
    return gcd(b, a%b)
}
/*
generates Farey sequence of order `n`
we don't equip a one-by-one approach,
rather will brute-forcely generate and then sort them out.
*/
func genFareySeq(n int) (ret fareySeq) {
    added := make(map[float64]bool) //check flag if already added or not
    for b := 1; b <= n; b++ {
        for a := 0; a <= b; a++ {
            key := float64(a) / float64(b)
            _, check := added[key]
            if !check {
                //Note that we append farey fractions sequentially,
                //which means a pair (a,b) with gcd>1 was already appended
                //no need to execute the following code
                //gcd := gcd(a, b)
                //x, y := a/gcd, b/gcd
                //ret = append(ret, farey{x, y})
                ret = append(ret, farey{a, b})
                added[key] = true
            }
        }
    }
    sort.Slice(ret, func(i, j int) bool {
        //a_i/b_i < a_j/b_j
        return ret[i].a*ret[j].b < ret[j].a*ret[i].b
    })
    return ret
}
// extend farey sequence of order `n` upto n/1 by reversely appending
func genExtendedFareySeq(n int) (ret fareySeq) {
    ret = genFareySeq(n)
    for i := len(ret) - 2; i > 0; i-- {
        ret = append(ret, farey{ret[i].b, ret[i].a})
    }
    return ret
}
type point struct {
    x, y int
}
type points []point
func (pts points) output() {
    fmt.Fprintln(writer, len(pts))
    for _, p := range pts {
        fmt.Fprintf(writer, "%d %d\n", p.x, p.y)
    }
}
// mirrors the given point `p` on an axis determined by the matrix
// [`mx` ,   0 ]
// [  0  , `my`]
func mirror(p point, mx, my int) point {
    return point{mx * p.x, my * p.y}
}
// checks if the mirror function does nothing
func notMirrored(p point, mx, my int) bool {
    return (p.x == mx*p.x) && (p.y == my*p.y)
}
// mirror the entire points `pts`
func mirrorPts(pts points, mx, my int) points {
    start := len(pts) - 1
    //no reflection point should be added
    if notMirrored(pts[start], mx, my) {
        start--
    }
    for i := start; i >= 0; i-- {
        pts = append(pts, mirror(pts[i], mx, my))
    }
    return pts
}
// build a convex hull with almost 4*len(`exfseq`) vertices
// like the following with v its starting point and goes counter-clockwise
//
//     _____
//    /     \
//   /       \
//  |         |
//   \       /
//    \__v__/
func construct(exfseq fareySeq) (ret points) {
    x, y := 0, -exfseq.height()
    ret = append(ret, point{x, y})
    //the horizontal slope 0/1 ought to be removed
    //because with mirroring, it can cause a degenerate triangle
    for i := 1; i < len(exfseq); i++ {
        x = x + exfseq[i].b
        y = y + exfseq[i].a
        ret = append(ret, point{x, y})
    }
    //we just mirror aquired points on x-axis and then y-axis
    //since it's already convex so we don't need to calculate.
    ret = mirrorPts(ret, 1, -1)
    ret = mirrorPts(ret, -1, 1)
    // just in case, if starting position == ending position
    if ret[0] == ret[len(ret)-1] {
        ret = ret[:len(ret)-1]
    }
    // cut to `N` if the aquired convex hull has more than `N` vertices.
    // we can do this because removing points from a convex hull doesn't
    // make a convex hull concave.
    if len(ret) > N {
        ret = ret[:N]
    }
    return ret
}
func main() {
    defer writer.Flush()
    fseq := genExtendedFareySeq(Order)
    ans := construct(fseq)
    ans.output()
}
func init() {
    writer = bufio.NewWriter(os.Stdout)
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0