結果
問題 | No.325 マンハッタン距離2 |
ユーザー |
|
提出日時 | 2020-04-10 19:09:24 |
言語 | Java (openjdk 23) |
結果 |
AC
|
実行時間 | 53 ms / 1,000 ms |
コード長 | 3,829 bytes |
コンパイル時間 | 2,223 ms |
コンパイル使用メモリ | 78,132 KB |
実行使用メモリ | 36,992 KB |
最終ジャッジ日時 | 2024-09-15 08:40:22 |
合計ジャッジ時間 | 4,643 ms |
ジャッジサーバーID (参考情報) |
judge6 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 24 |
ソースコード
import java.io.IOException;import java.io.InputStream;import java.math.BigInteger;import java.util.Arrays;import java.util.NoSuchElementException;public class Main {public static void main(String[] args) {new Main().run();}long gcd(long a,long b) {return a==0?b:gcd(b%a,a);}long h(long a,long b) {return (gcd(a,b)+(a+1)*(b+1))/2+1;}long g(long d,long x,long y) {if (x<0||y<0||d<0) return 0;if (x+y<=d) return (x+1)*(y+1);return (x+1)*(y+1)-h(x+y-d,x+y-d)+x+y-d+1;}long f(long x1,long y1,long d,long x2,long y2) {x2=Math.min(x2, x1+d);y2=Math.min(y2, y1+d);return g(d,x2-x1,y2-y1);}long f_brute(long x1,long y1,long d,long x2,long y2) {long ret=0;for (long x=x1;x<=x1+d;++x) {for (long y=y1;y<=y1+d;++y) {long dx=x-x1;long dy=y-y1;if (dx+dy>d) continue;if (x<=x2&&y<=y2) ++ret;}}return ret;}void run() {FastScanner sc=new FastScanner();long x1=sc.nextLong();long y1=sc.nextLong();long x2=sc.nextLong();long y2=sc.nextLong();long d=sc.nextLong();x2=Math.min(x2, +d);y2=Math.min(y2, +d);x1=Math.max(x1, -d);y1=Math.max(y1, -d);long ans=0;if (x1<=0&&0<=x2&&y1<=0&&0<=y2)++ans;ans+=f(Math.max(+x1, 1),Math.max(0,+y1),d-(Math.max(+x1, 1)+Math.max(0,+y1)),+x2,+y2);//第1象限ans+=f(Math.max(-x2, 0),Math.max(1,+y1),d-(Math.max(-x2, 0)+Math.max(1,+y1)),-x1,+y2);//第2象限ans+=f(Math.max(-x2, 1),Math.max(0,-y2),d-(Math.max(-x2, 1)+Math.max(0,-y2)),-x1,-y1);//第3象限ans+=f(Math.max(+x1, 0),Math.max(1,-y2),d-(Math.max(+x1, 0)+Math.max(1,-y2)),+x2,-y1);//第4象限System.out.println(ans);}void tr(Object...objects) {System.out.println(Arrays.deepToString(objects));}}class FastScanner {private final InputStream in = System.in;private final byte[] buffer = new byte[1024];private int ptr = 0;private int buflen = 0;private boolean hasNextByte() {if (ptr < buflen) {return true;}else{ptr = 0;try {buflen = in.read(buffer);} catch (IOException e) {e.printStackTrace();}if (buflen <= 0) {return false;}}return true;}private int readByte() { if (hasNextByte()) return buffer[ptr++]; else return -1;}private static boolean isPrintableChar(int c) { return 33 <= c && c <= 126;}public boolean hasNext() { while(hasNextByte() && !isPrintableChar(buffer[ptr])) ptr++; return hasNextByte();}public String next() {if (!hasNext()) throw new NoSuchElementException();StringBuilder sb = new StringBuilder();int b = readByte();while(isPrintableChar(b)) {sb.appendCodePoint(b);b = readByte();}return sb.toString();}public long nextLong() {if (!hasNext()) throw new NoSuchElementException();long n = 0;boolean minus = false;int b = readByte();if (b == '-') {minus = true;b = readByte();}if (b < '0' || '9' < b) {throw new NumberFormatException();}while(true){if ('0' <= b && b <= '9') {n *= 10;n += b - '0';}else if(b == -1 || !isPrintableChar(b)){return minus ? -n : n;}else{throw new NumberFormatException();}b = readByte();}}public int nextInt() {long nl = nextLong();if (nl < Integer.MIN_VALUE || nl > Integer.MAX_VALUE) throw new NumberFormatException();return (int) nl;}public double nextDouble() { return Double.parseDouble(next());}}