結果
問題 | No.245 貫け! |
ユーザー | ぴろず |
提出日時 | 2015-07-17 22:54:17 |
言語 | Java19 (openjdk 21) |
結果 |
AC
|
実行時間 | 2,336 ms / 5,000 ms |
コード長 | 1,978 bytes |
コンパイル時間 | 2,546 ms |
コンパイル使用メモリ | 79,808 KB |
実行使用メモリ | 67,736 KB |
最終ジャッジ日時 | 2023-09-22 18:00:46 |
合計ジャッジ時間 | 29,394 ms |
ジャッジサーバーID (参考情報) |
judge14 / judge11 |
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 233 ms
58,692 KB |
testcase_01 | AC | 278 ms
59,708 KB |
testcase_02 | AC | 281 ms
59,876 KB |
testcase_03 | AC | 231 ms
59,100 KB |
testcase_04 | AC | 272 ms
60,076 KB |
testcase_05 | AC | 327 ms
61,936 KB |
testcase_06 | AC | 390 ms
62,548 KB |
testcase_07 | AC | 211 ms
59,660 KB |
testcase_08 | AC | 768 ms
66,620 KB |
testcase_09 | AC | 1,022 ms
65,880 KB |
testcase_10 | AC | 1,072 ms
65,768 KB |
testcase_11 | AC | 1,576 ms
65,348 KB |
testcase_12 | AC | 2,223 ms
61,444 KB |
testcase_13 | AC | 2,165 ms
61,532 KB |
testcase_14 | AC | 2,127 ms
61,188 KB |
testcase_15 | AC | 2,336 ms
67,736 KB |
testcase_16 | AC | 2,136 ms
64,268 KB |
testcase_17 | AC | 2,020 ms
61,448 KB |
testcase_18 | AC | 2,166 ms
67,080 KB |
testcase_19 | AC | 2,082 ms
63,932 KB |
ソースコード
package no245; import java.util.ArrayList; import java.util.Collections; import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int n = sc.nextInt(); Vector2[][] seg = new Vector2[n][2]; for(int i=0;i<n;i++) { seg[i][0] = new Vector2(sc.nextLong(), sc.nextLong()); seg[i][1] = new Vector2(sc.nextLong(), sc.nextLong()); } int ans = 0; for(int i=0;i<=200;i++) { for(int j=-200;j<=200;j++) { if (i == 0 && j == 0) { continue; } Vector2 d = new Vector2(i, j); ArrayList<Event> al = new ArrayList<>(); for(int k=0;k<n;k++) { long x1 = seg[k][0].dot(d); long x2 = seg[k][1].dot(d); al.add(new Event(Math.min(x1, x2), 1)); al.add(new Event(Math.max(x1, x2), -1)); } Collections.sort(al); int sum = 0; for(Event e:al) { sum += e.a; ans = Math.max(ans, sum); } } } System.out.println(ans); } } class Event implements Comparable<Event>{ long x,a; public Event(long x,long a) { this.x = x; this.a = a; } public int compareTo(Event o) { if (x != o.x) { return Long.compare(x, o.x); } return - Long.compare(a, o.a); } public String toString() { return "[" + x + "," + a + "]"; } } class Vector2 { long x = 0; long y = 0; public Vector2(long x,long y) { this.x = x; this.y = y; } public long dot(Vector2 v) { return this.x*v.x+this.y*v.y; } public long cross(Vector2 v) { return this.x*v.y-this.y*v.x; } public Vector2 add(Vector2 v) { return new Vector2(this.x+v.x,this.y+v.y); } public Vector2 subtract(Vector2 v) { return new Vector2(this.x-v.x,this.y-v.y); } public Vector2 multiply(long k) { return new Vector2(k*this.x,k*this.y); } public String toString() { return this.x + " " + this.y; } public boolean equals(Object o) { if (o instanceof Vector2) { Vector2 v = (Vector2) o; return x == v.x && y == v.y; } return super.equals(o); } }