結果
問題 | No.5009 Draw A Convex Polygon |
ユーザー |
![]() |
提出日時 | 2022-12-10 00:30:39 |
言語 | Go (1.23.4) |
結果 |
WA
|
実行時間 | - |
コード長 | 3,649 bytes |
コンパイル時間 | 4,123 ms |
実行使用メモリ | 65,488 KB |
スコア | 0 |
平均クエリ数 | 1000001.00 |
最終ジャッジ日時 | 2022-12-10 00:30:48 |
合計ジャッジ時間 | 5,508 ms |
ジャッジサーバーID (参考情報) |
judge14 / judge15 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | WA * 1 |
ソースコード
/*https://yukicoder.me/problems/no/5009This program aims to solve the above competitive programming problemusing 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 mainimport ("bufio""fmt""os""sort")var writer *bufio.Writerconst (N = 1_000_000 // upper limit number of points// the number of 641-th Farey sequence enough to cover `N`/8// according to OEIS(A005728), see https://oeis.org/A005728Order = 641)// Farey fractiontype farey struct {a, b int // `a`/`b`, `b`!=0 and supposed to be coprime}// Farey sequencetype fareySeq []farey// sum of all numerators and denominators in the sequence,// will be used to determine where to begin an output sequencefunc (fseq fareySeq) height() (ret int) {for _, f := range fseq {ret += f.aret += f.b}return ret}// computes the greatest common divisor of a and bfunc gcd(a, b int) int {if b == 0 {return a}return gcd(b, a%b)}/*generates Farey sequence of order `n`, excluding 0/1 and 1/1.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) //for already added check flagfor 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_jreturn ret[i].a*ret[j].b < ret[j].a*ret[i].b})// remove the first 0/1 and the last 1/1// to avoid making a degenerate triangleret = ret[1 : len(ret)-1]return ret}type point struct {x, y int}type points []pointfunc (pts points) output() {fmt.Fprintln(writer, len(pts))for _, p := range pts {fmt.Fprintf(writer, "%d %d\n", p.x, p.y)}}// where to movetype direction struct {x, y intsteep bool //slop's steepness}type directions []direction// build a convex hull with almost 8*len(`fseq`) vertices like the following// where v is the starting point and goes counter-clockwise//// _____// / \// / \// | |// \ /// \__v__/func construct(fseq fareySeq) (ret points) {x, y := 0, -fseq.height() //initial pointret = append(ret, point{x, y})dirs := directions{direction{1, 1, false},direction{1, 1, true},direction{-1, 1, true},direction{-1, 1, false},direction{-1, -1, false},direction{-1, -1, true},direction{1, -1, true},direction{1, -1, false},}for _, d := range dirs {for i := 0; i < len(fseq); i++ {// we can get steepy slope by inversing a farey fractionif d.steep {x = x + d.x*fseq[i].ay = y + d.y*fseq[i].b} else {x = x + d.x*fseq[i].by = y + d.y*fseq[i].a}ret = append(ret, point{x, y})}}// if starting position == ending positionif 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 := genFareySeq(Order)ans := construct(fseq)ans.output()}func init() {writer = bufio.NewWriter(os.Stdout)}