結果
問題 |
No.1041 直線大学
|
ユーザー |
![]() |
提出日時 | 2021-03-17 13:47:52 |
言語 | Java (openjdk 23) |
結果 |
AC
|
実行時間 | 173 ms / 2,000 ms |
コード長 | 2,154 bytes |
コンパイル時間 | 2,756 ms |
コンパイル使用メモリ | 80,784 KB |
実行使用メモリ | 42,120 KB |
最終ジャッジ日時 | 2024-11-16 08:11:39 |
合計ジャッジ時間 | 9,120 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 37 |
ソースコード
import java.util.*; public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int n = sc.nextInt(); Point[] points = new Point[n]; for (int i = 0; i < n; i++) { points[i] = new Point(sc.nextInt(), sc.nextInt()); } int max = 2; for (int i = 0; i < n - 1; i++) { HashMap<Point, Integer> sums = new HashMap<>(); for (int j = i + 1; j < n; j++) { Point p = points[i].get(points[j]); p.normalize(); sums.put(p, sums.getOrDefault(p, 0) + 1); } for (int x : sums.values()) { max = Math.max(max, x + 1); } } System.out.println(max); } static class Point { int x; int y; public Point(int x, int y) { this.x = x; this.y = y; } public Point get(Point p) { return new Point(x - p.x, y - p.y); } public void normalize() { if (x == 0) { y = 1; return; } if (y == 0) { x = 1; return; } boolean isMinus = false; if (x < 0) { x *= -1; isMinus ^= true; } if (y < 0) { y *= -1; isMinus ^= true; } int gcd = getGCD(x, y); x /= gcd; y /= gcd; if (isMinus) { y *= -1; } } private int getGCD(int a, int b) { if (a % b == 0) { return b; } else { return getGCD(b, a % b); } } public int hashCode() { return x + y; } public boolean equals(Object o) { Point p = (Point)o; return p.x == x && p.y == y; } public String toString() { return x + ":" + y; } } }