/* 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) }