結果

問題 No.5009 Draw A Convex Polygon
ユーザー urutomurutom
提出日時 2022-12-12 01:47:27
言語 Go
(1.22.1)
結果
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
純コード判定しない問題か言語
このコードへのチャレンジ
（要ログイン）

テストケース

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

ソースコード

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