import java.util.*; import java.io.*; import java.util.stream.*; /* 사각형이 교차하면 펜을 안떼고 그냥그릴 수 있음 Union-Find로 풀 수 있을 것 같은데 */ class Rectangle { int x1, y1, x2, y2; public Rectangle(int x1, int y1, int x2, int y2) { this.x1 = Math.min(x1, x2); this.x2 = Math.max(x1, x2); this.y1 = Math.min(y1, y2); this.y2 = Math.max(y1, y2); } boolean isOnOrigin() { return ((y1 == 0 || y2 == 0) && (x1 <= 0 && 0 <= x2)) || ((x1 == 0 || x2 == 0) && (y1 <= 0 && 0 <= y2)); } boolean isCrossed(Rectangle other) { return !(other.x2 < this.x1 || other.x1 > this.x2 || other.y2 < this.y1 || other.y1 > this.y2); } boolean isIncludedBy(Rectangle other) { return (this.x1 > other.x1 && this.x2 < other.x2 && this.y1 > other.y1 && this.y2 < other.y2); } @Override public String toString() { return String.format("%d %d %d %d", x1, y1, x2, y2); } } public class Main { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); StringTokenizer st; int N; Rectangle[] arr; int[] unf; void solution() throws IOException { N = Integer.parseInt(br.readLine()); // 축을 처리하기 위해 사각형 두개를 더 넣자. arr = new Rectangle[N]; for (int i = 0; i < N; i++) { st = new StringTokenizer(br.readLine()); int x1 = Integer.parseInt(st.nextToken()); int y1 = Integer.parseInt(st.nextToken()); int x2 = Integer.parseInt(st.nextToken()); int y2 = Integer.parseInt(st.nextToken()); arr[i] = new Rectangle(x1, y1, x2, y2); } unf = new int[N]; for (int i = 0; i < N; i++) unf[i] = i; int bonus = 0; for (int i = 0; i < N; i++) { if (arr[i].isOnOrigin()) { bonus = 1; break; } } for (int i = 0; i < N; i++) { for (int j = i+1; j < N; j++) { if (arr[i].isCrossed(arr[j]) && !arr[i].isIncludedBy(arr[j]) && !arr[j].isIncludedBy(arr[i])) { union(i, j); } } } //find 함수를 이용해 집합의 갯수를 카운트한다. Set set = new HashSet<>(); for (int i = 0; i < N; i++) { set.add(find(i)); } System.out.println(set.size()-bonus); } int find(int a) { if (a == unf[a]) return a; return unf[a] = find(unf[a]); } void union(int a, int b) { int fa = find(a); int fb = find(b); if (fa != fb) unf[fa] = fb; } public static void main(String[] args) throws IOException { //System.setOut(new CustomPrintStream(System.out)); // 백준 제출할 때 이 부분을 주석처리하고 제출. try { Main main = new Main(); main.solution(); } catch (Exception e) { e.printStackTrace(); System.exit(1); } System.out.flush(); } } class CustomPrintStream extends PrintStream { private static final int MAX_OUTPUT_SIZE = 262142; private final StringBuilder buffer = new StringBuilder(); public CustomPrintStream(PrintStream out) { super(out); } // All print methods @Override public void print(boolean b) { buffer.append(b); } @Override public void print(char c) { buffer.append(c); } @Override public void print(int i) { buffer.append(i); } @Override public void print(long l) { buffer.append(l); } @Override public void print(float f) { buffer.append(f); } @Override public void print(double d) { buffer.append(d); } @Override public void print(char[] s) { buffer.append(s); } @Override public void print(String s) { buffer.append(s); } @Override public void print(Object obj) { buffer.append(obj); } // All println methods @Override public void println(boolean x) { buffer.append(x); buffer.append("\n"); } @Override public void println(char x) { buffer.append(x); buffer.append("\n"); } @Override public void println(int x) { buffer.append(x); buffer.append("\n"); } @Override public void println(long x) { buffer.append(x); buffer.append("\n"); } @Override public void println(float x) { buffer.append(x); buffer.append("\n"); } @Override public void println(double x) { buffer.append(x); buffer.append("\n"); } @Override public void println(char[] x) { buffer.append(x); buffer.append("\n"); } @Override public void println(String x) { buffer.append(x); buffer.append("\n"); } @Override public void println(Object x) { buffer.append(x); buffer.append("\n"); } @Override public void println() { buffer.append("\n"); } @Override public void flush() { if (buffer.length() > MAX_OUTPUT_SIZE) { throw new ExceedMaxOutputLimit("출력 용량을 초과하였습니다."); } super.print(buffer); buffer.setLength(0); } } class ExceedMaxOutputLimit extends RuntimeException { public ExceedMaxOutputLimit(String message) { super(message); } }

코드 #1702