글 읽기 - 어디가 틀렸을까요?

nrcrzl93 3년 전 0

안녕하세요.

답은 맞는데, 계속 틀리다고 나와서요

고수님들 혹시 도움좀 주실 수 있으실까요?

package hong2;

import java.io.BufferedReader;

import java.io.IOException;

import java.io.InputStreamReader;

import java.util.HashSet;

import java.util.StringTokenizer;

public class P2162 {

static int[] p;

public static void main(String[] args) throws NumberFormatException, IOException {

// TODO Auto-generated method stub

BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

int N = Integer.parseInt(br.readLine());

StringTokenizer stk;

p = new int[N];

Line[] line = new Line[N];

for (int i = 0; i < N; i++) {

p[i] = i;

stk = new StringTokenizer(br.readLine());

long x1 = Long.parseLong(stk.nextToken());

long y1 = Long.parseLong(stk.nextToken());

long x2 = Long.parseLong(stk.nextToken());

long y2 = Long.parseLong(stk.nextToken());

line[i] = new Line(new Point(x1, y1), new Point(x2, y2));

}

for (int i = 0; i < N; i++) {

for (int j = 0; j < N; j++) {

if (i == j) {

continue;

} else {

if (isCross(line[i], line[j])) {

// System.out.println("UNION : + union(" + i + ", " + j + ")");

union(i, j);

}

}

}

}

HashSet hs = new HashSet();

for (int i = 0; i < N; i++) {

// System.out.println("P[" + i + "] : " + p[i]);

hs.add(p[i]);

}

int result = 0;

for (int child : hs) {

int cnt = 0;

for (int i = 0; i < N; i++) {

if (p[i] == child) {

cnt++;

}

}

result = Math.max(result, cnt);

}

StringBuffer sb = new StringBuffer();

sb.append(Integer.toString(hs.size()));

sb.append("\n");

sb.append(Integer.toString(result));

System.out.println(sb.toString());

}

// p[i] = a p의 부모는 a다.

public static int find(int x) {

int i = x;

if (p[i] == i) {

return i;

} else {

return p[i] = find(p[i]);

}

}

public static void union(int x, int y) {

int a = find(x);

int b = find(y);

if (p[a] > p[b]) {

p[b] = a;

} else {

p[a] = b;

}

}

public static long ccw(Point p1, Point p2, Point p3) {

long result = (p1.x * p2.y + p2.x * p3.y + p3.x * p1.y) - (p2.x * p1.y + p3.x * p2.y + p1.x * p3.y);

if (result > 0) {

return 1;

} else if (result < 0) {

return -1;

} else {

return 0;

}

}

private static boolean isCross(Line l1, Line l2) {

long ab = ccw(l1.p1, l1.p2, l2.p1) * ccw(l1.p1, l1.p2, l2.p2);

long cd = ccw(l2.p1, l2.p2, l1.p1) * ccw(l2.p1, l2.p2, l1.p2);

if (!(ab == 0 && cd == 0)) {

return isOverlapped(l1, l2);

}

return ab <= 0 && ab <= 0;

}

private static boolean isOverlapped(Line l1, Line l2) {

if (Math.max(l1.p1.x, l1.p2.x) < Math.min(l2.p1.x, l2.p2.x)) {

return false;

}

if (Math.min(l1.p1.x, l1.p2.x) > Math.max(l2.p1.x, l2.p2.x)) {

return false;

}

if (Math.max(l1.p1.y, l1.p2.y) < Math.min(l2.p1.y, l2.p2.y)) {

return false;

}

if (Math.min(l1.p1.y, l1.p2.y) > Math.max(l2.p1.y, l2.p2.y)) {

return false;

}

return true;

}

public static class Point {

long x;

long y;

public Point(long x, long y) {

this.x = x;

this.y = y;

}

}

public static class Line {

Point p1;

Point p2;

public Line(Point p1, Point p2) {

this.p1 = p1;

this.p2 = p2;

}

}

}

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

어디가 틀렸을까요?

nrcrzl93 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말