結果

問題 No.325 マンハッタン距離2
ユーザー ぴろず
提出日時 2015-12-20 18:40:55
言語 Java
(openjdk 23)
結果
AC  
実行時間 138 ms / 1,000 ms
コード長 3,489 bytes
コンパイル時間 2,539 ms
コンパイル使用メモリ 87,368 KB
実行使用メモリ 41,724 KB
最終ジャッジ日時 2024-09-17 12:19:53
合計ジャッジ時間 7,051 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 24
権限があれば一括ダウンロードができます

ソースコード

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);
        if (e.size() == 0) {
            System.out.println(0);
            return;
        }
//      System.out.println(e);
        long sum = 0;
        for(int i=0;i<e.size()-1;i++) {
            long xa = e.get(i) + 1;
            long xb = e.get(i+1) - 1;
            if (xa > xb) {
                continue;
            }
            long c1 = count(xa,y1,y2,d);
            long c2 = count(xb,y1,y2,d);
//          System.out.println("[" + xa + "," + xb + "]:" + c1 + "->" + c2 + ":" + ((c1 + c2) * (xb - xa + 1) / 2));
            sum += (c1 + c2) * (xb - xa + 1) / 2;
        }
        for(long x:e) {
//          System.out.println(x + ":" + count(x,y1,y2,d));
            sum += count(x,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 + ")";
    }
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0