## Problem B Battle Royale

#include <bits/stdc++.h>
typedef double db;
const db eps = 1e-9;

namespace Geometry {
int Sgn(db k) {return fabs(k) < eps ? 0 : (k < 0 ? -1 : 1);}
int Cmp(db k1, db k2) {return Sgn(k1 - k2);}
db max(db k1, db k2) {return Cmp(k1, k2) > 0 ? k1 : k2;}
db min(db k1, db k2) {return Cmp(k1, k2) < 0 ? k1 : k2;}
struct point {db x, y;};
point operator + (point k1, point k2) {return (point){k1.x + k2.x, k1.y + k2.y};}
point operator - (point k1, point k2) {return (point){k1.x - k2.x, k1.y - k2.y};}
db operator * (point k1, point k2) {return k1.x * k2.x + k1.y * k2.y;}
db operator ^ (point k1, point k2) {return k1.x * k2.y - k1.y * k2.x;}
db GetDisP2P(point k1, point k2) {return sqrt((k2 - k1) * (k2 - k1));}
db GetAng(point k1, point k2) {return fabs(atan2(fabs(k1 ^ k2), k1 * k2));}
struct line {point s, t;};
typedef line seg;
db GetLen(seg k) {return sqrt((k.t - k.s) * (k.t - k.s));}
db GetDisP2Line(point k1, line k2) {return fabs((k1 - k2.s) ^ (k2.t - k2.s)) / GetLen(k2);}
db GetDisP2Seg(point k1, seg k2) {
if (Sgn((k1 - k2.s) * (k2.t - k2.s)) < 0 || Sgn((k1 - k2.t) * (k2.s - k2.t)) < 0) {
return min(GetDisP2P(k1, k2.s), GetDisP2P(k1, k2.t));
}
return GetDisP2Line(k1, k2);
}
struct circle {point o; db r;};
}
using namespace Geometry;

int main() {
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr); std::cout.tie(nullptr);
std::cout << std::fixed << std::setprecision(10);

point s, t;
std::cin >> s.x >> s.y;
std::cin >> t.x >> t.y;
circle blue, red;
std::cin >> blue.o.x >> blue.o.y >> blue.r;
std::cin >> red.o.x >> red.o.y >> red.r;

if (Cmp(GetDisP2Seg(red.o, (seg){s, t}), red.r) >= 0) {
std::cout << GetDisP2P(s, t) << '\n';
return 0;
}

db dis_o2s = GetDisP2P(red.o, s), dis_o2t = GetDisP2P(red.o, t);
db ang = GetAng(s - red.o, t - red.o) - acos(red.r / dis_o2s) - acos(red.r / dis_o2t);
db ans = sqrt(dis_o2s * dis_o2s - red.r * red.r) + sqrt(dis_o2t * dis_o2t - red.r * red.r);
ans += ang * red.r;

std::cout << ans << '\n';
return 0;
}

## Problem C Coolest Ski Route

#include <bits/stdc++.h>

struct edge {int pre, c;};
std::vector<std::vector<edge>> g;
std::vector<bool> vis;
std::vector<int> dis;

int Dfs(int u) {
if (vis[u]) return dis[u];
int ret = 0;
for (auto &e : g[u]) {
ret = std::max(ret, Dfs(e.pre) + e.c);
}
vis[u] = true;
dis[u] = ret;
return ret;
}

int main() {
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr); std::cout.tie(nullptr);

int n, m; std::cin >> n >> m;
g.resize(n);
for (int i = 0, u, v, c; i < m; ++i) {
std::cin >> u >> v >> c;
--u; --v;
g[v].push_back((edge){u, c});
}

int ans = 0;
vis.assign(n, false);
dis.assign(n, 0);
for (int i = 0; i < n; ++i) {
if (!vis[i]) ans = std::max(ans, Dfs(i));
}

std::cout << ans << '\n';
return 0;
}

#include <bits/stdc++.h>
const int maxn = 1e7 + 5;

bool is_prime[maxn];
std::vector<int> prime;

void Sieve() {
memset(is_prime, true, sizeof(is_prime));
for (long long i = 2; i < maxn; ++i) {
if (is_prime[i]) prime.emplace_back(i);
for (auto &p : prime) {
if (p * i >= maxn) break;
is_prime[i * p] = false;
}
}
is_prime[0] = is_prime[1] = false;
}

int main() {
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr); std::cout.tie(nullptr);

Sieve();

int t; std::cin >> t;
for (int cas = 1; cas <= t; ++cas) {
std::string a, b; std::cin >> a >> b;

long long n = 0, m = 0;
for (auto &s : a) if (isdigit(s)) n = n * 10 + (s - '0');
for (auto &s : b) if (isdigit(s)) m = m * 10 + (s - '0');

long long gcd = std::__gcd(n, m);
n /= gcd; m /= gcd;

if (n == m) std::cout << 2 << ' ' << 2 << '\n';
else if (is_prime[n] && is_prime[m]) std::cout << n << ' ' << m << '\n';
else std::cout << "impossible\n";
}
return 0;
}

## Problem I It's Time for a Montage

$n$ 个 $1\sim n$ 级别的英雄和 $n$ 个 $1\sim n$ 级别的怪兽，高级别英雄可以击败任意低等级怪兽，当级别相同时英雄攻击力大于等于怪兽时才可将其击败，每训练一天英雄攻击力 $+1$ ，求击败怪兽最少训练天数

#include <bits/stdc++.h>

int n;
std::vector<int> h;
std::vector<int> v;

bool Check(int x) {
for (int i = 0; i < n; ++i) {
if (h[i] + x < v[i]) return false;
if (h[i] + x > v[i]) return true;
}
return true;
}

int main() {
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr); std::cout.tie(nullptr);

std::cin >> n;
h.assign(n, 0); v.assign(n, 0);
for (auto &it : h) std::cin >> it;
for (auto &it : v) std::cin >> it;

int l = 0, r = 1e3 + 5, ans;
while (l <= r) {
int m = (l + r) >> 1;
if (Check(m)) {
ans = m;
r = m - 1;
}
else l = m + 1;
}

std::cout << ans << '\n';
return 0;
}

## Problem L Logic Puzzle

$n$ 行 $m$ 列的扫雷棋盘（扩大一圈给出）， 求地雷分布图

#include <bits/stdc++.h>

std::vector<std::vector<int>> clue;
std::vector<std::vector<bool>> col;

void Change(int x, int y) {
for (int i = -1; i < 2; ++i) {
for (int j = -1; j < 2; ++j) {
if (clue[x + i][y + j] <= 0) return;
}
}
col[x][y] = true;
for (int i = -1; i < 2; ++i) {
for (int j = -1; j < 2; ++j) {
--clue[x + i][y + j];
}
}
}

int main() {
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr); std::cout.tie(nullptr);

int h, w; std::cin >> h >> w;
clue = std::vector<std::vector<int>>(h + 2, std::vector<int>(w + 2, 0));
for (int i = 0; i < h + 2; ++i)
for (int j = 0; j < w + 2; ++j)
std::cin >> clue[i][j];

col = std::vector<std::vector<bool>>(h + 2, std::vector<bool>(w + 2, false));

int cir = (std::min(h, w) + 1) / 2;
int l = 1, r = w, t = 1, b = h;
for (int k = 0; k < cir; ++k) {
Change(t, l); Change(t, r);
Change(b, l); Change(b, r);

int m = (l + r + 1) / 2;

for (int i = l + 1; i < m; ++i) Change(t, i);
for (int i = r - 1; i >= m; --i) Change(t, i);
for (int i = l + 1; i < m; ++i) Change(b, i);
for (int i = r - 1; i >= m; --i) Change(b, i);

m = (t + b + 1) / 2;

for (int i = t + 1; i < m; ++i) Change(i, l);
for (int i = b - 1; i >= m; --i) Change(i, l);
for (int i = t + 1; i < m; ++i) Change(i, r);
for (int i = b - 1; i >= m; --i) Change(i, r);

if (l != r) {
++l;
--r;
}
if (t != b) {
++t;
--b;
}
}

for (int i = 0; i < h + 2; ++i) {
for (int j = 0; j < w + 2; ++j) {
if (clue[i][j] > 0) {
std::cout << "impossible\n";
return 0;
}
}
}

for (int i = 1; i <= h; ++i) {
for (int j = 1; j <= w; ++j) {
std::cout << (col[i][j] ? 'X' : '.');
}
std::cout << '\n';
}
return 0;
}
Last modification：April 4th, 2019 at 09:58 pm