[BOJ] 5884. Three Lines (bruteforce)

[BOJ] 5884. Three Lines (bruteforce)

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173

import java.io. * ; import java.util. * ; public class Main { FastScanner in ; PrintWriter out ; static class Point implements Comparable < Point > { int x, y; public Point( int x, int y) { this .x = x; this .y = y; } public void switching() { int tmp = this .x; this .x = this .y; this .y = tmp; } /** * order by x asc, y asc */ @Override public int compareTo(Point p) { if ( this .x = = p.x) { return Integer.compare( this .y, p.y); } else { return Integer.compare( this .x, p.x); } } } static int N, cntCamera = 0 ; static Map < Integer, Integer > cntCowByLine; static List < Point > cowsList; void solve() { N = in .nextInt(); cowsList = new ArrayList < > (); // 1. 모든 소의 좌표 저장 for ( int i = 0 ; i < N; i + + ) { int x = in .nextInt(); int y = in .nextInt(); cowsList. add ( new Point(x, y)); } // 2. X 좌표 기준 정렬 cowsList.sort( null ); // 3. 모든 소의 수평선에 카메라 설치 setCameraOnY(); // 4. x 좌표에 중복이 있고 y 좌표에 중복이 없는 수직선에 카메라 설치 setCameraOnX(); // 5. 최대 세 개의 감시 카메라로 모든 소를 감시할 수 있는지 확인 if (isPossible()) { out . println ( 1 ); return ; } // 6. x, y 좌표 바꿔서 다시 수행 cntCamera = 0 ; for (Point p : cowsList) p.switching(); cowsList.sort( null ); setCameraOnY(); setCameraOnX(); if (isPossible()) { out . println ( 1 ); } else { out . println ( 0 ); } } private void setCameraOnY() { cntCowByLine = new HashMap < > (); // y 좌표 기준으로 소가 있는 모든 수평선에 카메라를 설치하면서 해당 수평선에 몇 마리의 소가 있는지 카운트 for (Point p : cowsList) { if (cntCowByLine.get(p.y) = = null ) { cntCowByLine.put(p.y, 1 ); cntCamera + + ; } else { cntCowByLine.put(p.y, cntCowByLine.get(p.y) + 1 ); } } } private void setCameraOnX() { int xLine = - 1 ; // x 좌표 기준으로 소가 있는 모든 수직선을 확인하면서 해당 수직선에 카메라를 설치할지 체크 for (Point p : cowsList) { // 해당 점의 수평선에 다른 소가 있는 경우 패스. if (cntCowByLine.get(p.y) > 1 ) continue ; // 해당 점의 수평선에 다른 소가 없는 경우 // 이전에 설치한 수직선과 같은 라인에 있다면 수평선에 설치된 카메라를 없애주자 if (xLine = = p.x) { cntCamera - - ; } else { // 수직선에 새로 카메라를 설치할 경우 xLine = p.x; } } } private Boolean isPossible() { // 모든 소를 감시하기 위해 카메라가 3대 넘게 설치될 경우 실패 if (cntCamera > 3 ) { return false ; } else { return true ; } } /********************************** Input function **********************************/ void run() { in = new FastScanner(); out = new PrintWriter( System . out ); solve(); out .close(); } public static void main( String [] args) { new Main().run(); } class FastScanner { BufferedReader br; StringTokenizer st; public FastScanner() { br = new BufferedReader( new InputStreamReader( System . in )); } public FastScanner( String s) { try { br = new BufferedReader( new FileReader(s)); } catch (FileNotFoundException e) { e.printStackTrace(); } } String nextToken() { while (st = = null | | ! st.hasMoreElements()) { try { st = new StringTokenizer(br.readLine()); } catch (IOException e) { e.printStackTrace(); } } return st.nextToken(); } int nextInt() { return Integer. parseInt (nextToken()); } long nextLong() { return Long.parseLong(nextToken()); } double nextDouble() { return Double.parseDouble(nextToken()); } } } Colored by Color Scripter

from http://data-make.tistory.com/688 by ccl(A) rewrite - 2021-09-17 23:27:50