結果

問題 No.5007 Steiner Space Travel
ユーザー allegrogiken
提出日時 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`

ソースコード

diff #
プレゼンテーションモードにする

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