using System; using System.Collections.Generic; using System.Diagnostics; using System.IO; using System.Linq; using System.Numerics; using System.Runtime.CompilerServices; using static System.Math; partial class Program { static int[] dx = new int[] { 1, 0, -1, 0, 1, -1, -1, 1 }; static int[] dy = new int[] { 0, 1, 0, -1, 1, 1, -1, -1 }; const long mod = 1000000007; //const long mod = 998244353; static Random rnd = new Random(); static Stopwatch sw = new Stopwatch(); static long A = 5; public void Solve() { sw.Start(); var (N, M) = io.GetMulti(); var planets = io.GetIntArray(N).Select((e, id) => new Pos(e[0], e[1], id)).ToArray(); Console.Clear(); var K = M; var means = planets.Take(K).ToList(); var assignments = new int[N]; while (true) { var prevAssignments = assignments.Select(v => v).ToArray(); for (int i = 0; i < N; i++) { var minId = -1; var min = long.MaxValue; for (int j = 0; j < K; j++) { if (min.Chmin(means[j].Length(planets[i]))) minId = j; } assignments[i] = minId; } if (Enumerable.Range(0, N).All(i => assignments[i] == prevAssignments[i])) break; for (int k = 0; k < K; k++) { long tx = 0; long ty = 0; var cnt = 0; for (int i = 0; i < N; i++) { if (assignments[i] != k) continue; tx += planets[i].x; ty += planets[i].y; cnt++; } if (cnt == 0) { means[k] = planets[rnd.Next(N)]; } means[k] = new Pos(tx / cnt, ty / cnt, -1); } } var stations = new Pos[M]; for (int i = 0; i < M; i++) { stations[i] = new Pos(means[i].x, means[i].y, N + i); } var G = (long.MaxValue / 3).Repeat(N + M, N + M); for (int i = 0; i < N + M; i++) G[i][i] = 0; var dijkstra = new Dijkstra(N); for (int i = 0; i < N; i++) { for (int j = 0; j < N; j++) { if (i == j) continue; G[i][j] = planets[i].Length(planets[j]); dijkstra.AddDirectedEdge(i, j, planets[i].Length(planets[j])); } } var len = new long[N][]; var path = new int[N][][]; for (int i = 0; i < N; i++) { len[i] = dijkstra.GetDist(i); path[i] = new int[N][]; for (int j = 0; j < N; j++) path[i][j] = dijkstra.GetPath(j); } var now = 0; var visited = new bool[N]; visited[0] = true; var visitedCnt = 1; var ans = new List(); ans.Add(planets[0]); long S = 0; while (visitedCnt != N) { var next = -1; var min = long.MaxValue; for (int i = 0; i < N; i++) { if (visited[i]) continue; if (min.Chmin(len[now][i])) next = i; } S += min; ans.AddRange(path[now][next].Select(e => planets[e])); visited[next] = true; visitedCnt++; now = next; } ans.AddRange(path[now][0].Select(e => planets[e])); S += len[now][0]; TSP(ans); var newAns = new List(); foreach (var a in ans) { if (newAns.Count == 0 || newAns.Last().id != a.id) newAns.Add(a); } ans = newAns; var bestList = ans; var bestScore = Score(ans, stations); var nowScore = bestScore; var bestStations = stations.ToArray(); var yamaCnt = 0; var yakinamashi = new YakinamashiManager(sw); while (sw.ElapsedMilliseconds < 880) { yamaCnt++; if (yamaCnt % 1000 == 0) { yakinamashi.Update(); } var sidx = rnd.Next(M); var oldX = stations[sidx].x; var oldY = stations[sidx].y; int deltaL = (int)(300 * (900 - sw.ElapsedMilliseconds) / sw.ElapsedMilliseconds); int deltaS = (int)(100 * (900 - sw.ElapsedMilliseconds) / sw.ElapsedMilliseconds); var delta = rnd.Next(deltaS, deltaL); var nx = oldX + rnd.Next(-delta, delta); var ny = oldY + rnd.Next(-delta, delta); stations[sidx].x = nx; stations[sidx].y = ny; var ng = false; for (int i = 0; i < M; i++) { if (i == sidx) continue; } if (ng) { stations[sidx].x = oldX; stations[sidx].y = oldY; continue; } var score = Score(bestList, stations); //if (!bestScore.Chmax(score)) if (!yakinamashi.Trans(score - nowScore)) { stations[sidx].x = oldX; stations[sidx].y = oldY; } else { nowScore = score; if (bestScore.Chmax(nowScore)) Array.Copy(stations, bestStations, M); } } Array.Copy(bestStations, stations, M); newAns = new List(); newAns.Add(planets[0]); for (int i = 0; i < bestList.Count - 1; i++) { var p = planets[bestList[i].id]; var next = planets[bestList[i + 1].id]; var l = p.Length(next); var min = long.MaxValue; var s = -1; for (int j = 0; j < M; j++) { if (l.Chmin(p.Length(stations[j]))) s = j; } if (s != -1) newAns.Add(stations[s]); newAns.Add(next); } ans = newAns; TSP(ans); for (int i = 0; i < M; i++) io.Print($"{stations[i].x} {stations[i].y}"); Console.WriteLine(ans.Count); for (int i = 0; i < ans.Count; i++) Console.WriteLine($"{1 + ans[i].id / N} {ans[i].id % N + 1}"); } long Score(long length) { return (long)Round(1000000000 / (1000 + Sqrt(length))); } long Score(List arr, Pos[] stations) { long sum = 0; for (int i = 0; i < arr.Count - 1; i++) { var min = arr[i].Length(arr[i + 1]); for (int j = 0; j < 5; j++) { min.Chmin(arr[i].Length(stations[j]) + stations[j].Length(arr[i + 1])); } sum += min; } return Score(sum); } class YakinamashiManager { Stopwatch sw; double st = 0, dt = 900; double nt, T; Random rand = new Random(); public YakinamashiManager(Stopwatch _sw) { sw = _sw; Update(); } public void Update() { nt = (sw.ElapsedMilliseconds - st) / (dt - st); T = Math.Pow(T0, 1 - nt) * Math.Pow(T1, nt); } double T0 = 100; double T1 = 0; public bool Trans(long delta) { var p = Math.Pow(E, delta / T); return rand.NextDouble() < Math.Pow(E, delta / T); } } class Dijkstra { public Dijkstra(int V) { this.V = V; G = new List<(int to, long dist)>[V]; for (int i = 0; i < V; i++) { G[i] = new List<(int to, long dist)>(); } from = new int[this.V]; } long _INF = long.MaxValue; int V; List<(int to, long dist)>[] G; int[] from; /// /// 無向辺を追加します。 /// public void AddEdge(int u, int v, long dist) { G[u].Add((v, dist)); G[v].Add((u, dist)); } /// /// 有向辺を追加します。 /// public void AddDirectedEdge(int from, int to, long dist) { G[from].Add((to, dist)); } /// /// 各頂点への最短経路長を求めます。 /// 計算量はO((E+V)logV)です。 /// public long[] GetDist(int s) { var dist = new long[V]; dist.AsSpan().Fill(_INF); from = new int[V]; from.AsSpan().Fill(-1); var pq = new PriorityQueue(); dist[s] = 0; pq.Enqueue(0, s); while (pq.Count > 0) { var (d, v) = pq.Dequeue(); if (dist[v] != d) continue; foreach (var edge in G[v]) { var alt = d + edge.dist; if (alt >= dist[edge.to]) continue; dist[edge.to] = alt; from[edge.to] = v; pq.Enqueue(alt, edge.to); } } for (int i = 0; i < V; i++) if (dist[i] == _INF) dist[i] = -1; return dist; } public int[] GetPath(int t) { var now = t; var ls = new List(); while (from[t] != -1) { ls.Add(t); t = from[t]; } ls.Reverse(); return ls.ToArray(); } } class PriorityQueue { /// /// 空の優先度付きキューを生成します。 /// public PriorityQueue() { _keys = new List(); _elements = new List(); } List _keys; List _elements; /// /// 優先度付きキューに要素を追加します。 /// 計算量は O(log(要素数)) です。 /// public void Enqueue(long key, T elem) { var n = _elements.Count; _keys.Add(key); _elements.Add(elem); while (n != 0) { var i = (n - 1) / 2; if (_keys[n] < _keys[i]) { (_keys[n], _keys[i]) = (_keys[i], _keys[n]); (_elements[n], _elements[i]) = (_elements[i], _elements[n]); } n = i; } } /// /// 頂点要素を返し、削除します。 /// 計算量は O(log(要素数)) です。 /// public (long key, T value) Dequeue() { var t = Peek(); Pop(); return t; } void Pop() { var n = _elements.Count - 1; _elements[0] = _elements[n]; _elements.RemoveAt(n); _keys[0] = _keys[n]; _keys.RemoveAt(n); for (int i = 0, j; (j = 2 * i + 1) < n;) { //左の子と右の子で右の子の方が優先度が高いなら右の子を処理したい if ((j != n - 1) && _keys[j] > _keys[j + 1]) j++; //親より子が優先度が高いなら親子を入れ替える if (_keys[i] > _keys[j]) { (_keys[i], _keys[j]) = (_keys[j], _keys[i]); (_elements[i], _elements[j]) = (_elements[j], _elements[i]); } i = j; } } /// /// 頂点要素を返します。 /// 計算量は O(1) です。 /// public (long key, T value) Peek() => (_keys[0], _elements[0]); /// /// 優先度付きキューに格納されている要素の数を返します。 /// 計算量は O(1) です。 /// public int Count => _elements.Count; /// /// 要素が存在するかを返します。 /// /// public bool Any() => _elements.Any(); } struct Pos { public long x; public long y; public int id; static private readonly long N = 100; public Pos(long _x, long _y, int _id) { x = _x; y = _y; id = _id; } public long Length(Pos pos) { return (id >= N ? 1 : 5) * (pos.id >= N ? 1 : 5) * ((pos.x - x) * (pos.x - x) + (pos.y - y) * (pos.y - y)); } override public string ToString() => $"{x} {y}"; } void TSP(List pos) { var cnt = 0; var ccnt = 0; while (cnt < 100000) { cnt++; var a = rnd.Next(pos.Count - 1); var b = rnd.Next(pos.Count - 1); if (a == b) continue; if (a > b) (a, b) = (b, a); var ap = pos[a]; var bp = pos[b]; var cp = pos[(b + 1) % pos.Count]; var dp = pos[a + 1]; var diff = (ap.Length(dp) + bp.Length(cp) - ap.Length(bp) - cp.Length(dp)); if (diff > 0) { ccnt++; var (x, y) = (a + 1, b); while (x < y) { (pos[x], pos[y]) = (pos[y], pos[x]); x++; y--; } } } } IO io = new IO(); static void Main() { Console.SetIn(new StreamReader(Console.OpenStandardInput(8192))); Console.SetOut(new StreamWriter(Console.OpenStandardOutput()) { AutoFlush = false }); var program = new Program(); //var t = new Thread(program.Solve, 134217728); //t.Start(); //t.Join(); program.Solve(); Console.Out.Flush(); Console.Read(); } } //------------------------------------------------------------------------------------------------------------------ public static class Ex { public static bool IsNullOrEmpty(this string s) { return string.IsNullOrEmpty(s); } public static void yesno(this bool b) => Console.WriteLine(b ? "yes" : "no"); public static void YesNo(this bool b) => Console.WriteLine(b ? "Yes" : "No"); public static void YESNO(this bool b) => Console.WriteLine(b ? "YES" : "NO"); public static void Yes() => Console.WriteLine("Yes"); public static void YES() => Console.WriteLine("YES"); public static void No() => Console.WriteLine("No"); public static void NO() => Console.WriteLine("NO"); public static void M1() => Console.WriteLine("-1"); public static void TakahashiAoki(this bool b) => Console.WriteLine(b ? "Takahashi" : "Aoki"); [MethodImpl(MethodImplOptions.AggressiveInlining)] public static bool Chmax(ref this int a, int b) { if (a < b) { a = b; return true; } else return false; } [MethodImpl(MethodImplOptions.AggressiveInlining)] public static bool Chmin(ref this int a, int b) { if (a > b) { a = b; return true; } else return false; } [MethodImpl(MethodImplOptions.AggressiveInlining)] public static bool Chmax(ref this long a, long b) { if (a < b) { a = b; return true; } else return false; } [MethodImpl(MethodImplOptions.AggressiveInlining)] public static bool Chmin(ref this long a, long b) { if (a > b) { a = b; return true; } else return false; } [MethodImpl(MethodImplOptions.AggressiveInlining)] public static bool Chmin(ref this long a, long b) { if (a > b) { a = b; return true; } else return false; } [MethodImpl(MethodImplOptions.AggressiveInlining)] public static bool Chmax(ref this T a, T b) where T : struct, IComparable { if (b.CompareTo(a) > 0) { a = b; return true; } else return false; } [MethodImpl(MethodImplOptions.AggressiveInlining)] public static bool Chmin(ref this T a, T b) where T : struct, IComparable { if (b.CompareTo(a) < 0) { a = b; return true; } else return false; } /// /// constraintを満たす最小のインデックスを返します。 /// /// T key が満たすべき制約 /// 制約を満たす最小のインデックス(0-indexed) public static int LowerBound(this IList ls, Func constraint) { var ng = -1; var ok = ls.Count; while (ok - ng > 1) { var mid = (ok + ng) / 2; if (constraint(ls[mid])) ok = mid; else ng = mid; } return ok; } public static void Swap(this IList arr, int a, int b) => (arr[a], arr[b]) = (arr[b], arr[a]); public static long[] GetCum(this IList ls) { var res = new long[ls.Count + 1]; for (int i = 0; i < ls.Count; i++) res[i + 1] = res[i] + ls[i]; return res; } public static T[] GetCum(this IList ls, bool fromLeft, T gen, Func func) { var res = new T[ls.Count + 1]; res.AsSpan().Fill(gen); if (fromLeft) { for (int i = 0; i < ls.Count; i++) res[i + 1] = func(res[i], ls[i]); } else { for (int i = ls.Count; i > 0; i--) res[i - 1] = func(res[i], ls[i - 1]); } return res; } public static T[] Repeat(this T element, int N) { var res = new T[N]; res.AsSpan().Fill(element); return res; } public static T[][] Repeat(this T element, int H, int W) { var res = new T[H][]; for (int i = 0; i < H; i++) { res[i] = new T[W]; res[i].AsSpan().Fill(element); } return res; } public static T[][][] Repeat(this T element, int H, int W, int R) { var res = new T[H][][]; for (int i = 0; i < H; i++) { res[i] = new T[W][]; for (int j = 0; j < W; j++) { res[i][j] = new T[R]; res[i][j].AsSpan().Fill(element); } } return res; } } class IO { public string GetStr() => Console.ReadLine().Trim(); public char GetChar() => Console.ReadLine().Trim()[0]; public int GetInt() => int.Parse(Console.ReadLine().Trim()); public long GetLong() => long.Parse(Console.ReadLine().Trim()); public double GetDouble() => double.Parse(Console.ReadLine().Trim()); public decimal GetDecimal() => decimal.Parse(Console.ReadLine().Trim()); public string[] GetStrArray() => Console.ReadLine().Trim().Split(' '); public string[][] GetStrArray(int N) { var res = new string[N][]; for (int i = 0; i < N; i++) res[i] = Console.ReadLine().Trim().Split(' '); return res; } public int[] GetIntArray() => Console.ReadLine().Trim().Split(' ').Select(int.Parse).ToArray(); public int[][] GetIntArray(int N) { var res = new int[N][]; for (int i = 0; i < N; i++) res[i] = Console.ReadLine().Trim().Split(' ').Select(int.Parse).ToArray(); return res; } public long[] GetLongArray() => Console.ReadLine().Trim().Split(' ').Select(long.Parse).ToArray(); public long[][] GetLongArray(int N) { var res = new long[N][]; for (int i = 0; i < N; i++) res[i] = Console.ReadLine().Trim().Split(' ').Select(long.Parse).ToArray(); return res; } public decimal[] GetDecimalArray() => Console.ReadLine().Trim().Split(' ').Select(decimal.Parse).ToArray(); public decimal[][] GetDecimalArray(int N) { var res = new decimal[N][]; for (int i = 0; i < N; i++) res[i] = Console.ReadLine().Trim().Split(' ').Select(decimal.Parse).ToArray(); return res; } public char[] GetCharArray() => Console.ReadLine().Trim().Split(' ').Select(char.Parse).ToArray(); public double[] GetDoubleArray() => Console.ReadLine().Trim().Split(' ').Select(double.Parse).ToArray(); public double[][] GetDoubleArray(int N) { var res = new double[N][]; for (int i = 0; i < N; i++) res[i] = Console.ReadLine().Trim().Split(' ').Select(double.Parse).ToArray(); return res; } public char[][] GetGrid(int H) { var res = new char[H][]; for (int i = 0; i < H; i++) res[i] = Console.ReadLine().Trim().ToCharArray(); return res; } public List[] GetUnweightedAdjanceyList(int V, int E, bool isDirected, bool isNode_0indexed) { var ls = new List[V]; for (int i = 0; i < V; i++) ls[i] = new List(); for (int i = 0; i < E; i++) { var input = Console.ReadLine().Split(' ').Select(int.Parse).ToArray(); if (isNode_0indexed == false) { input[0]--; input[1]--; } ls[input[0]].Add(input[1]); if (isDirected == false) ls[input[1]].Add(input[0]); } return ls; } public List<(int to, long dist)>[] GetWeightedAdjacencyList(int V, int E, bool isDirected, bool isNode_0indexed) { var ls = new List<(int to, long dist)>[V]; for (int i = 0; i < V; i++) ls[i] = new List<(int to, long dist)>(); for (int i = 0; i < E; i++) { var hoge = Console.ReadLine().Split(' '); var a = int.Parse(hoge[0]); var b = int.Parse(hoge[1]); var c = long.Parse(hoge[2]); if (isNode_0indexed == false) { a--; b--; } ls[a].Add((b, c)); if (isDirected == false) ls[b].Add((a, c)); } return ls; } [MethodImpl(MethodImplOptions.AggressiveInlining)] bool eq() => typeof(T).Equals(typeof(U)); [MethodImpl(MethodImplOptions.AggressiveInlining)] T ct(U a) => (T)Convert.ChangeType(a, typeof(T)); [MethodImpl(MethodImplOptions.AggressiveInlining)] T cv(string s) => eq() ? ct(int.Parse(s)) : eq() ? ct(long.Parse(s)) : eq() ? ct(double.Parse(s)) : eq() ? ct(decimal.Parse(s)) : eq() ? ct(s[0]) : ct(s); [MethodImpl(MethodImplOptions.AggressiveInlining)] void Multi(out T a) => a = cv(GetStr()); [MethodImpl(MethodImplOptions.AggressiveInlining)] void Multi(out T a, out U b) { var ar = GetStrArray(); a = cv(ar[0]); b = cv(ar[1]); } [MethodImpl(MethodImplOptions.AggressiveInlining)] void Multi(out T a, out U b, out V c) { var ar = GetStrArray(); a = cv(ar[0]); b = cv(ar[1]); c = cv(ar[2]); } [MethodImpl(MethodImplOptions.AggressiveInlining)] void Multi(out T a, out U b, out V c, out W d) { var ar = GetStrArray(); a = cv(ar[0]); b = cv(ar[1]); c = cv(ar[2]); d = cv(ar[3]); } [MethodImpl(MethodImplOptions.AggressiveInlining)] void Multi(out T a, out U b, out V c, out W d, out X e) { var ar = GetStrArray(); a = cv(ar[0]); b = cv(ar[1]); c = cv(ar[2]); d = cv(ar[3]); e = cv(ar[4]); } [MethodImpl(MethodImplOptions.AggressiveInlining)] void Multi(out T a, out U b, out V c, out W d, out X e, out Y f) { var ar = GetStrArray(); a = cv(ar[0]); b = cv(ar[1]); c = cv(ar[2]); d = cv(ar[3]); e = cv(ar[4]); f = cv(ar[5]); } [MethodImpl(MethodImplOptions.AggressiveInlining)] public (T, U) GetMulti() { var ar = Console.ReadLine().Split(' '); return (cv(ar[0]), cv(ar[1])); } [MethodImpl(MethodImplOptions.AggressiveInlining)] public (T, U, V) GetMulti() { var ar = Console.ReadLine().Split(' '); return (cv(ar[0]), cv(ar[1]), cv(ar[2])); } [MethodImpl(MethodImplOptions.AggressiveInlining)] public (T, U, V, W) GetMulti() { var ar = Console.ReadLine().Split(' '); return (cv(ar[0]), cv(ar[1]), cv(ar[2]), cv(ar[3])); } [MethodImpl(MethodImplOptions.AggressiveInlining)] public (T, U, V, W, X) GetMulti() { var ar = Console.ReadLine().Split(' '); return (cv(ar[0]), cv(ar[1]), cv(ar[2]), cv(ar[3]), cv(ar[4])); } [MethodImpl(MethodImplOptions.AggressiveInlining)] public (T, U, V, W, X, Y) GetMulti() { var ar = Console.ReadLine().Split(' '); return (cv(ar[0]), cv(ar[1]), cv(ar[2]), cv(ar[3]), cv(ar[4]), cv(ar[5])); } [MethodImpl(MethodImplOptions.AggressiveInlining)] public void Print() => Console.WriteLine(); [MethodImpl(MethodImplOptions.AggressiveInlining)] public void Print(T t) => Console.WriteLine(t); [MethodImpl(MethodImplOptions.AggressiveInlining)] public void Print(string separator, IList ls) => Console.WriteLine(string.Join(separator, ls)); public void Debug(IList ls) { Console.Error.WriteLine(); Console.Error.WriteLine("[" + string.Join(",", ls) + "]"); } public void Debug(IList> ls) { Console.Error.WriteLine(); foreach (var l in ls) { Console.Error.WriteLine("[" + string.Join(",", l) + "]"); } Console.Error.WriteLine(); } }