結果
問題 | No.5007 Steiner Space Travel |
ユーザー |
|
提出日時 | 2022-07-30 16:00:49 |
言語 | D (dmd 2.109.1) |
結果 |
AC
|
実行時間 | 2 ms / 1,000 ms |
コード長 | 4,695 bytes |
コンパイル時間 | 2,982 ms |
実行使用メモリ | 3,444 KB |
スコア | 5,783,012 |
最終ジャッジ日時 | 2023-06-01 00:00:00 |
合計ジャッジ時間 | 4,710 ms |
ジャッジサーバーID (参考情報) |
judge15 / judge11 |
純コード判定しない問題か言語 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 30 |
コンパイルメッセージ
/dmd2/linux/bin64/../../src/phobos/std/numeric.d(2967): Warning: cannot inline function `std.numeric.gcdImpl!ulong.gcdImpl`
ソースコード
void main() { runSolver(); }// ----------------------------------------------enum long ALPHA = 5;enum ALPHAS = [0, 0, 1, ALPHA, ALPHA^^2];alias Vector = Vector2!long;struct Spot {int type, id;Vector location;long energy(Spot other) {auto k = ALPHAS[type + other.type];return location.norm(other.location) * k;}string toString() {return "%s %s".format(type, id);}}enum long BOUNDARY = 10 ^^ 3;Vector center(Vector[] arr) {long x = arr.map!"a.x".sum / arr.length;long y = arr.map!"a.y".sum / arr.length;return Vector(x, y);}Vector center(Spot[] arr) {long x = arr.map!"a.location.x".sum / arr.length;long y = arr.map!"a.location.y".sum / arr.length;return Vector(x, y);}auto degComp(Spot as, Spot bs, Vector center) {auto a = as.location;auto b = bs.location;auto d1 = atan2(a.y.to!real - center.y.to!real, a.x.to!real - center.x.to!real);auto d2 = atan2(b.y.to!real - center.y.to!real, b.x.to!real - center.x.to!real);return d1 < d2;}void problem() {auto N = scan!int;auto M = scan!int;auto P = N.iota.map!(_ => Vector(scan!long, scan!long)).array;auto rnd = Xorshift(unpredictableSeed);auto solve() {auto allCenter = center(P);auto targets = P.enumerate(1).map!(p => Spot(1, p[0], p[1])).array;targets.sort!((a, b) => degComp(a, b, allCenter));auto startIndex = targets.countUntil!(t => t.id == 1);targets = targets[startIndex..$] ~ targets[0..startIndex];auto stationIndicies = 0 ~ iota(1, M + 1).map!(m => N * m / M).array;auto stations = M.iota.map!(i => Spot(2, i + 1, center(targets[stationIndicies[i]..stationIndicies[i + 1]])));string[] ans;foreach(s; stations) ans ~= s.location.toString;string[] routes;foreach(si; 0..M) {foreach(i; stationIndicies[si]..stationIndicies[si + 1]) {routes ~= targets[i].toString;routes ~= stations[si].toString;}}routes ~= targets[0].toString;ans ~= routes.length.to!string;ans ~= routes;return ans;}outputForAtCoder(&solve);}// ----------------------------------------------import std.stdio, std.conv, std.array, std.string, std.algorithm, std.container, std.range, std.math, std.typecons, std.numeric, std.traits, std.functional, std.bigint, std.datetime.stopwatch, core.time, core.bitop, std.random;string scan(){ static string[] ss; while(!ss.length) ss = readln.chomp.split; string res = ss[0]; ss.popFront; return res; }T scan(T)(){ return scan.to!T; }T[] scan(T)(long n){ return n.iota.map!(i => scan!T()).array; }void deb(T ...)(T t){ debug { write("#"); writeln(t); }}T[] divisors(T)(T n) { T[] ret; for (T i = 1; i * i <= n; i++) { if (n % i == 0) { ret ~= i; if (i * i != n) ret ~= n / i; } } return ret.sort.array;}bool chmin(T)(ref T a, T b) { if (b < a) { a = b; return true; } else return false; }bool chmax(T)(ref T a, T b) { if (b > a) { a = b; return true; } else return false; }string charSort(alias S = "a < b")(string s) { return (cast(char[])((cast(byte[])s).sort!S.array)).to!string; }ulong comb(ulong a, ulong b) { if (b == 0) {return 1;}else{return comb(a - 1, b - 1) * a / b;}}string toAnswerString(R)(R r) { return r.map!"a.to!string".joiner(" ").array.to!string; }void outputForAtCoder(T)(T delegate() fn) {static if (is(T == float) || is(T == double) || is(T == real)) "%.16f".writefln(fn());else static if (is(T == void)) fn();else static if (is(T == string)) fn().writeln;else static if (isInputRange!T) {static if (!is(string == ElementType!T) && isInputRange!(ElementType!T)) foreach(r; fn()) r.toAnswerString.writeln;else foreach(r; fn()) r.writeln;}else fn().writeln;}void runSolver() {enum BORDER = "#==================================";debug { BORDER.writeln; while(true) { "#<<< Process time: %s >>>".writefln(benchmark!problem(1)); BORDER.writeln; } }else problem();}enum YESNO = [true: "Yes", false: "No"];// -----------------------------------------------struct Vector2(T) {T x, y;Vector2 add(Vector2 other) { return Vector2(x + other.x, y + other.y ); }Vector2 opAdd(Vector2 other) { return add(other); }Vector2 sub(Vector2 other) { return Vector2(x - other.x, y - other.y ); }Vector2 opSub(Vector2 other) { return sub(other); }T norm(Vector2 other) {return (x - other.x)*(x - other.x) + (y - other.y)*(y - other.y); }T dot(Vector2 other) {return x*other.y - y*other.x; }Vector2 normalize() {if (x == 0 || y == 0) return Vector2(x == 0 ? 0 : x/x.abs, y == 0 ? 0 : y/y.abs);const gcd = x.abs.gcd(y.abs);return Vector2(x/ gcd, y / gcd);}string toString() { return "%s %s".format(x, y); }}