結果

問題 No.325 マンハッタン距離2
ユーザー ぴろずぴろず
提出日時 2015-12-20 18:18:42
言語 Java21
(openjdk 21)
結果
WA  
実行時間 -
コード長 3,399 bytes
コンパイル時間 2,499 ms
コンパイル使用メモリ 80,940 KB
実行使用メモリ 41,480 KB
最終ジャッジ日時 2024-09-17 12:19:46
合計ジャッジ時間 6,954 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge2
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 116 ms
40,192 KB
testcase_01 AC 116 ms
39,848 KB
testcase_02 AC 134 ms
41,252 KB
testcase_03 AC 128 ms
41,108 KB
testcase_04 AC 129 ms
41,252 KB
testcase_05 AC 130 ms
41,064 KB
testcase_06 AC 129 ms
41,208 KB
testcase_07 WA -
testcase_08 AC 131 ms
41,244 KB
testcase_09 AC 128 ms
41,312 KB
testcase_10 AC 130 ms
41,064 KB
testcase_11 AC 119 ms
40,136 KB
testcase_12 AC 117 ms
40,316 KB
testcase_13 AC 131 ms
41,212 KB
testcase_14 AC 119 ms
40,360 KB
testcase_15 AC 128 ms
40,984 KB
testcase_16 AC 130 ms
40,972 KB
testcase_17 AC 129 ms
41,192 KB
testcase_18 AC 130 ms
41,072 KB
testcase_19 AC 128 ms
40,956 KB
testcase_20 RE -
testcase_21 AC 130 ms
41,124 KB
testcase_22 AC 131 ms
41,268 KB
testcase_23 AC 132 ms
41,056 KB
testcase_24 AC 129 ms
41,212 KB
testcase_25 AC 129 ms
41,076 KB
testcase_26 AC 129 ms
41,480 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

package no325;

import java.util.ArrayList;
import java.util.Scanner;
import java.util.TreeSet;

public class Main {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		long x1 = sc.nextLong();
		long y1 = sc.nextLong();
		long x2 = sc.nextLong();
		long y2 = sc.nextLong();
		long d = sc.nextLong();
		if (d == 0) {
			if (x1 <= 0 && 0 <= x2 && y1 <= 0 && 0 <= y2) {
				System.out.println(1);
			}else{
				System.out.println(0);
			}
			return;
		}
		Vector2[] sq1 = {new Vector2(x1,y1),new Vector2(x2,y1),new Vector2(x2,y2),new Vector2(x1,y2)};
		Vector2[] sq2 = {new Vector2(d,0),new Vector2(0,d),new Vector2(-d,0),new Vector2(0,-d)};
		TreeSet<Long> ee = new TreeSet<>();
		long rmin = Math.max(-d, x1);
		long rmax = Math.min(d, x2);
		long[] es = {x1,x2,0L,-d,d};
		for(long l:es) {
			rangeCheckAdd(ee, l, rmin, rmax);
		}
		for(int i=0;i<4;i++) {
			for(int j=0;j<4;j++) {
				Vector2 is = Vector2.intersect2(sq1[i], sq1[(i+1)%4], sq2[j], sq2[(j+1)%4]);
				rangeCheckAdd(ee, Math.round(is.x), rmin, rmax);
			}
		}
		ArrayList<Long> e = new ArrayList<>(ee);
//		System.out.println(e);
		long sum = 0;
		for(int i=0;i<e.size()-1;i++) {
			long xa = e.get(i);
			long xb = e.get(i+1);
			long c1 = count(xa,y1,y2,d);
			long c2 = count(xb,y1,y2,d);
//			if (Math.abs(c1-c2) < Math.abs(xa-xb)) {
//				continue;
//			}
//			System.out.println("[" + xa + "," + xb + "):" + c1 + "->" + c2 + ":" + ((c1 + c2) * (xb - xa + 1) / 2 - c2));
			sum += (c1 + c2) * (xb - xa + 1) / 2 - c2;
		}
		sum += count(e.get(e.size()-1),y1,y2,d);
		System.out.println(sum);
	}
	
	public static void rangeCheckAdd(TreeSet<Long> ts,long x,long min,long max) {
		if (min <= x && x <= max) {
			ts.add(x);
		}
	}
	
	//(a,b) (a=x,y1<=b<=y2) に、原点からマンハッタン距離がdイカの点がいくつ存在するか数える 
	public static long count(long x,long y1,long y2,long d) {
		long dy = d - Math.abs(x);
		if (dy < 0) {
			return 0;
		}
		if (y1 > dy || y2 < -dy) {
			return 0;
		}
		return Math.min(dy, y2) - Math.max(-dy, y1) + 1;
	}

}
class Vector2 {
	public double x;
	public double y;
	public Vector2(double x,double y) {
		this.x = x;
		this.y = y;
	}
	public double dot(Vector2 v) {
		return this.x*v.x+this.y*v.y;
	}
	public double cross(Vector2 v) {
		return this.x*v.y-this.y*v.x;
	}
	public double norm() {
		return Math.sqrt(this.x*this.x+this.y*this.y);
	}
	public Vector2 normalize() {
		return divide(norm());
	}
	public Vector2 add(Vector2 v) {
		return new Vector2(x+v.x,y+v.y);
	}
	public Vector2 subtract(Vector2 v) {
		return new Vector2(x-v.x,y-v.y);
	}
	public Vector2 multiply(double k) {
		return new Vector2(x*k,y*k);
	}
	public Vector2 divide(double k) {
		return new Vector2(x/k,y/k);
	}
	public Vector2 rotate90() {
		return new Vector2(-y,x);
	}
	public Vector2 rotate270() {
		return new Vector2(y,-x);
	}
	public static Vector2 intersect(Vector2 r1,Vector2 d1,Vector2 r2,Vector2 d2) {
		return r1.add(d1.multiply(-d2.cross(r2.subtract(r1)) / d1.cross(d2)));
	}
	public static Vector2 intersect2(Vector2 v11, Vector2 v12, Vector2 v21, Vector2 v22) {
		return Vector2.intersect(v11, v12.subtract(v11), v21, v22.subtract(v21));
	}
	public static double dist(Vector2 r1,Vector2 r2,Vector2 p) {
		return r2.subtract(r1).normalize().cross(p.subtract(r1));
	}
	public String toString() {
		return "(" + this.x + "," + this.y + ")";
	}
}
0