結果
| 問題 | No.245 貫け！ |
| ユーザー |
 suigingin
|
| 提出日時 | 2015-07-19 21:29:34 |
| 言語 | Java (openjdk 23) |
| 結果 |
AC
|
| 実行時間 | 165 ms / 5,000 ms |
| コード長 | 4,359 bytes |
| コンパイル時間 | 2,559 ms |
| コンパイル使用メモリ | 79,916 KB |
| 実行使用メモリ | 41,484 KB |
| 最終ジャッジ日時 | 2024-07-08 10:27:05 |
| 合計ジャッジ時間 | 6,342 ms |
|
ジャッジサーバーID （参考情報） |
judge2 / judge1 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 4 |
| other | AC * 16 |
ソースコード
import java.util.Arrays;import java.util.Scanner;public class Main {MyScanner sc = new MyScanner();Scanner sc2 = new Scanner(System.in);long start = System.currentTimeMillis();long fin = System.currentTimeMillis();final int MOD = 1000000007;int[] dx = { 1, 0, 0, -1 };int[] dy = { 0, 1, -1, 0 };int N;Point[][] p;void run() {N = sc.nextInt();p = pointArray(N);int max = 1;for (int i = 0; i < N; i++) {Point o1 = p[i][0];Point o2 = p[i][1];for (int j = 0; j < N; j++) {if (i == j) continue;Point p1 = p[j][0];Point p2 = p[j][1];if (o1.x != p1.x || o1.y != p1.y) max = Math.max(max, crossCnt(o1, p1, i, j));if (o1.x != p2.x || o1.y != p2.y) max = Math.max(max, crossCnt(o1, p2, i, j));if (o2.x != p1.x || o2.y != p1.y) max = Math.max(max, crossCnt(o2, p1, i, j));if (o2.x != p2.x || o2.y != p2.y) max = Math.max(max, crossCnt(o2, p2, i, j));}}System.out.println(max);}int crossCnt(Point s, Point t, int non1, int non2) {int cnt = 0;for (int i = 0; i < N; i++) {if (lineCross(s, t, p[i][0], p[i][1])) cnt++;}return cnt;}boolean lineCross(Point p1, Point p2, Point p3, Point p4) {int a = (p1.x - p2.x) * (p3.y - p1.y) + (p1.y - p2.y) * (p1.x - p3.x);int b = (p1.x - p2.x) * (p4.y - p1.y) + (p1.y - p2.y) * (p1.x - p4.x);return a * b <= 0;}class Point {int x;int y;public Point(int x, int y) {super();this.x = x;this.y = y;}}public Point[][] pointArray(int n) {Point[][] res = new Point[n][2];for (int i = 0; i < n; i++) {res[i][0] = new Point(sc.nextInt(), sc.nextInt());res[i][1] = new Point(sc.nextInt(), sc.nextInt());}return res;}public static void main(String[] args) {new Main().run();}void debug(Object... o) {System.out.println(Arrays.deepToString(o));}void debug2(int[][] array) {for (int i = 0; i < array.length; i++) {for (int j = 0; j < array[i].length; j++) {System.out.print(array[i][j]);}System.out.println();}}boolean inner(int h, int w, int limH, int limW) {return 0 <= h && h < limH && 0 <= w && w < limW;}void swap(int[] x, int a, int b) {int tmp = x[a];x[a] = x[b];x[b] = tmp;}// find minimum i (a[i] >= border)int lower_bound(int a[], int border) {int l = -1;int r = a.length;while (r - l > 1) {int mid = (l + r) / 2;if (border <= a[mid]) {r = mid;} else {l = mid;}}// r = l + 1return r;}boolean palindrome(String s) {for (int i = 0; i < s.length() / 2; i++) {if (s.charAt(i) != s.charAt(s.length() - 1 - i)) {return false;}}return true;}class MyScanner {int nextInt() {try {int c = System.in.read();while (c != '-' && (c < '0' || '9' < c))c = System.in.read();if (c == '-')return -nextInt();int res = 0;do {res *= 10;res += c - '0';c = System.in.read();} while ('0' <= c && c <= '9');return res;} catch (Exception e) {return -1;}}double nextDouble() {return Double.parseDouble(next());}long nextLong() {return Long.parseLong(next());}String next() {try {StringBuilder res = new StringBuilder("");int c = System.in.read();while (Character.isWhitespace(c))c = System.in.read();do {res.append((char) c);} while (!Character.isWhitespace(c = System.in.read()));return res.toString();} catch (Exception e) {return null;}}int[] nextIntArray(int n) {int[] in = new int[n];for (int i = 0; i < n; i++) {in[i] = nextInt();}return in;}int[][] nextInt2dArray(int n, int m) {int[][] in = new int[n][m];for (int i = 0; i < n; i++) {in[i] = nextIntArray(m);}return in;}double[] nextDoubleArray(int n) {double[] in = new double[n];for (int i = 0; i < n; i++) {in[i] = nextDouble();}return in;}long[] nextLongArray(int n) {long[] in = new long[n];for (int i = 0; i < n; i++) {in[i] = nextLong();}return in;}char[][] nextCharField(int n, int m) {char[][] in = new char[n][m];for (int i = 0; i < n; i++) {String s = sc.next();for (int j = 0; j < m; j++) {in[i][j] = s.charAt(j);}}return in;}}}