結果

問題 No.5009 Draw A Convex Polygon
ユーザー urutomurutom
提出日時 2022-12-10 00:30:39
言語 Go
(1.22.1)
結果
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
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 WA -
権限があれば一括ダウンロードができます

ソースコード

diff # 

/*
https://yukicoder.me/problems/no/5009
This program aims to solve the above competitive programming problem
using 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 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 numerators and 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.a
		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`, 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 flag
	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
	})
	// remove the first 0/1 and the last 1/1
	// to avoid making a degenerate triangle
	ret = ret[1 : len(ret)-1]
	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)
	}
}

// where to move
type direction struct {
	x, y  int
	steep 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 point
	ret = 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 fraction
			if d.steep {
				x = x + d.x*fseq[i].a
				y = y + d.y*fseq[i].b
			} else {
				x = x + d.x*fseq[i].b
				y = y + d.y*fseq[i].a
			}
			ret = append(ret, point{x, y})
		}
	}
	// 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 := genFareySeq(Order)
	ans := construct(fseq)
	ans.output()
}

func init() {
	writer = bufio.NewWriter(os.Stdout)
}
0