結果
| 問題 | No.960 マンハッタン距離3 |
| ユーザー |
👑  hos.lyric
|
| 提出日時 | 2019-12-25 18:38:55 |
| 言語 | D (dmd 2.109.1) |
| 結果 |
AC
|
| 実行時間 | 106 ms / 2,000 ms |
| コード長 | 7,751 bytes |
| コンパイル時間 | 1,510 ms |
| コンパイル使用メモリ | 130,536 KB |
| 実行使用メモリ | 17,084 KB |
| 最終ジャッジ日時 | 2024-06-22 04:03:19 |
| 合計ジャッジ時間 | 11,863 ms |
|
ジャッジサーバーID （参考情報） |
judge1 / judge5 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 4 |
| other | AC * 216 |
ソースコード
import std.conv, std.functional, std.range, std.stdio, std.string;
import std.algorithm, std.array, std.bigint, std.bitmanip, std.complex, std.container, std.math, std.mathspecial, std.numeric, std.regex, std.typecons;
import core.bitop;
class EOFException : Throwable { this() { super("EOF"); } }
string[] tokens;
string readToken() { for (; tokens.empty; ) { if (stdin.eof) { throw new EOFException; } tokens = readln.split; } auto token = tokens.front; tokens.popFront; return token; }
int readInt() { return readToken.to!int; }
long readLong() { return readToken.to!long; }
real readReal() { return readToken.to!real; }
bool chmin(T)(ref T t, in T f) { if (t > f) { t = f; return true; } else { return false; } }
bool chmax(T)(ref T t, in T f) { if (t < f) { t = f; return true; } else { return false; } }
int binarySearch(alias pred, T)(in T[] as) { int lo = -1, hi = cast(int)(as.length); for (; lo + 1 < hi; ) { const mid = (lo + hi) >> 1; (unaryFun!pred(as[mid]) ? hi : lo) = mid; } return hi; }
int lowerBound(T)(in T[] as, T val) { return as.binarySearch!(a => (a >= val)); }
int upperBound(T)(in T[] as, T val) { return as.binarySearch!(a => (a > val)); }
void main() {
try {
for (; ; ) {
const W = readLong();
const H = readLong();
const N = readInt();
auto X = new long[N];
auto Y = new long[N];
foreach (i; 0 .. N) {
X[i] = readLong();
Y[i] = readLong();
}
auto A = new long[N];
auto B = new long[N];
foreach (i; 0 .. N) {
A[i] = X[i] + Y[i];
B[i] = -X[i] + Y[i];
}
const as = A.dup.sort.uniq.array;
const bs = B.dup.sort.uniq.array;
debug {
writeln("A = ", A);
writeln("B = ", B);
writeln("as = ", as);
writeln("bs = ", bs);
}
bool check(long ca, long cb, long sz) {
const cx = (ca - cb) / 2;
const cy = (ca + cb) / 2;
if (!(1 <= cx && cx <= W && 1 <= cy && cy <= H)) {
return false;
}
foreach (i; 0 .. N) {
if (sz != max(abs(A[i] - ca), abs(B[i] - cb))) {
return false;
}
}
debug {
writeln("check ", ca, " ", cb, " ", sz, " = true");
}
return true;
}
long ans;
if (A.map!(a => (a & 1)).array.sort.uniq.array.length == 1 &&
B.map!(a => (a & 1)).array.sort.uniq.array.length == 1) {
if (as.length == 1 && bs.length == 1) {
ans = H * W;
} if (as.length == 1) {
/*
##
##
o
o
o
##
##
*/
const i0 = X.minIndex;
const i1 = X.maxIndex;
ans += (X[i0] - 1 + 1) * (Y[i1] - 1 + 1);
ans += (W - X[i1] + 1) * (H - Y[i0] + 1);
if (N == 2) {
ans += (X[i1] - X[i0] - 1);
}
} else if (bs.length == 1) {
/*
##
##
o
o
o
##
##
*/
const i0 = X.minIndex;
const i1 = X.maxIndex;
ans += (X[i0] - 1 + 1) * (H - Y[i1] + 1);
ans += (W - X[i1] + 1) * (Y[i0] - 1 + 1);
if (N == 2) {
ans += (X[i1] - X[i0] - 1);
}
} else {
// no as[0], as[$ - 1]
if (bs.length == 2) {
const sz = (bs[$ - 1] - bs[0]) / 2;
const cb = bs[0] + sz;
// x = 1 or y = 1
long aL = max(1 + (cb + 1), (1 - cb) + 1);
// x = W or y = H
long aU = min(W + (cb + W), (H - cb) + H);
foreach (i; 0 .. N) {
chmax(aL, A[i] - sz);
chmin(aU, A[i] + sz);
}
chmax(aL, as[$ - 1] - sz + 2);
chmin(aU, as[0] + sz - 2);
ans += max((aU - aL) / 2 + 1, 0);
}
// no bs[0], bs[$ - 1]
if (as.length == 2) {
const sz = (as[$ - 1] - as[0]) / 2;
const ca = as[0] + sz;
// x = W or y = 1
long bL = max(-W + (ca - W), -(ca - 1) + 1);
// x = 1 or y = H
long bU = min(-1 + (ca - 1), -(ca - H) + H);
foreach (i; 0 .. N) {
chmax(bL, B[i] - sz);
chmin(bU, B[i] + sz);
}
chmax(bL, bs[$ - 1] - sz + 2);
chmin(bU, bs[0] + sz - 2);
ans += max((bU - bL) / 2 + 1, 0);
}
// [as[0], *] x [bs[0], *]
{
long sz;
long yL = (as[0] + bs[0]) / 2;
foreach (i; 0 .. N) {
if (A[i] == as[0] || B[i] == bs[0]) {
chmax(yL, Y[i]);
} else {
chmax(sz, max(A[i] - as[0], B[i] - bs[0]) / 2);
}
}
if (sz) {
if (check(as[0] + sz, bs[0] + sz, sz)) ans += 1;
} else {
ans += max(H - yL + 1, 0);
}
}
// [as[0], *] x [*, bs[$ - 1]]
{
long sz;
long xL = (as[0] - bs[$ - 1]) / 2;
foreach (i; 0 .. N) {
if (A[i] == as[0] || B[i] == bs[$ - 1]) {
chmax(xL, X[i]);
} else {
chmax(sz, max(A[i] - as[0], bs[$ - 1] - B[i]) / 2);
}
}
if (sz) {
if (check(as[0] + sz, bs[$ - 1] - sz, sz)) ans += 1;
} else {
ans += max(W - xL + 1, 0);
}
}
// [as[0], *] x [bs[0], bs[$ - 1]]
{
const sz = (bs[$ - 1] - bs[0]) / 2;
if (check(as[0] + sz, bs[0] + sz, sz)) ans -= 1;
}
// [*, as[$ - 1]] x [bs[0], *]
{
long sz;
long xU = (as[$ - 1] - bs[0]) / 2;
foreach (i; 0 .. N) {
if (A[i] == as[$ - 1] || B[i] == bs[0]) {
chmin(xU, X[i]);
} else {
chmax(sz, max(as[$ - 1] - A[i], B[i] - bs[0]) / 2);
}
}
if (sz) {
if (check(as[$ - 1] - sz, bs[0] + sz, sz)) ans += 1;
} else {
ans += max(xU - 1 + 1, 0);
}
}
// [*, as[$ - 1]] x [*, bs[$ - 1]]
{
long sz;
long yU = (as[$ - 1] + bs[$ - 1]) / 2;
foreach (i; 0 .. N) {
if (A[i] == as[$ - 1] || B[i] == bs[$ - 1]) {
chmin(yU, Y[i]);
} else {
chmax(sz, max(as[$ - 1] - A[i], bs[$ - 1] - B[i]) / 2);
}
}
if (sz) {
if (check(as[$ - 1] - sz, bs[$ - 1] - sz, sz)) ans += 1;
} else {
ans += max(yU - 1 + 1, 0);
}
}
// [*, as[$ - 1]] x [bs[0], bs[$ - 1]]
{
const sz = (bs[$ - 1] - bs[0]) / 2;
if (check(as[$ - 1] - sz, bs[0] + sz, sz)) ans -= 1;
}
// [as[0], as[$ - 1]] x [bs[0], *]
{
const sz = (as[$ - 1] - as[0]) / 2;
if (check(as[0] + sz, bs[0] + sz, sz)) ans -= 1;
}
// [as[0], as[$ - 1]] x [*, bs[$ - 1]]
{
const sz = (as[$ - 1] - as[0]) / 2;
if (check(as[0] + sz, bs[$ - 1] - sz, sz)) ans -= 1;
}
// [as[0], as[$ - 1]] x [bs[0], bs[$ - 1]]
if (as[$ - 1] - as[0] == bs[$ - 1] - bs[0]) {
const sz = (as[$ - 1] - as[0]) / 2;
if (check(as[0] + sz, bs[0] + sz, sz)) ans += 1;
}
}
}
writeln(ans);
}
} catch (EOFException e) {
}
}