結果

問題 No.5009 Draw A Convex Polygon
ユーザー urutomurutom
提出日時 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
権限があれば一括ダウンロードができます

ソースコード

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