結果
| 問題 |
No.245 貫け！
|
| コンテスト | |
| ユーザー |
 suigingin
|
| 提出日時 | 2015-07-17 23:55:40 |
| 言語 | Java (openjdk 23) |
| 結果 |
WA
|
| 実行時間 | - |
| コード長 | 4,727 bytes |
| コンパイル時間 | 2,549 ms |
| コンパイル使用メモリ | 79,980 KB |
| 実行使用メモリ | 43,564 KB |
| 最終ジャッジ日時 | 2024-07-08 09:46:55 |
| 合計ジャッジ時間 | 5,405 ms |
|
ジャッジサーバーID （参考情報） |
judge1 / judge3 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 4 |
| other | AC * 9 WA * 7 |
ソースコード
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 = N >= 2 ? 2 : 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];
max = Math.max(max, crossCnt(o1, p1, i, j) + 2);
max = Math.max(max, crossCnt(o1, p2, i, j) + 2);
max = Math.max(max, crossCnt(o2, p1, i, j) + 2);
max = Math.max(max, crossCnt(o2, p2, i, j) + 2);
}
}
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 (i == non1 || i == non2)
continue;
if (lineCross(s, t, p[i][0], p[i][1])) {
cnt++;
}
}
return cnt;
}
boolean lineCross(Point p1, Point p2, Point p3, Point p4) {
double a = (p1.x - p2.x) * (p3.y - p1.y) + (p1.y - p2.y)
* (p1.x - p3.x);
double b = (p1.x - p2.x) * (p4.y - p1.y) + (p1.y - p2.y)
* (p1.x - p4.x);
double c = (p3.x - p4.x) * (p1.y - p3.y) + (p3.y - p4.y)
* (p3.x - p1.x);
double d = (p3.x - p4.x) * (p2.y - p3.y) + (p3.y - p4.y)
* (p3.x - p2.x);
return a * b <= 0;
}
class Point implements Comparable<Point> {
double x;
double y;
public Point(double x, double y) {
super();
this.x = x;
this.y = y;
}
@Override
public int compareTo(Point arg0) {
if (this.x == arg0.x)
return this.y - arg0.y > 0 ? 1 : -1;
if (this.x - arg0.x > 0)
return 1;
else
return -1;
}
}
public Point[][] pointArray(int n) {
Point[][] res = new Point[n][2];
for (int i = 0; i < n; i++) {
res[i][0] = new Point(sc.nextDouble(), sc.nextDouble());
res[i][1] = new Point(sc.nextDouble(), sc.nextDouble());
}
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 + 1
return 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;
}
}
}