6862번 Tin Can Telephone

문제

---

6862번 Tin Can Telephone - 백준

번역

---

깡통 전화라는 문제인데
한국인에겐 종이컵 전화가 더 익숙할 듯 하다.

깡통이든 종이컵이든 양 수화부를 쭉 펼쳐서 통화를 하려는데
경로에 건물이 있거나 닿으면 안된다.

입력을 받았을때 걸리적 거리는 건물의 수를 출력하시오.
건물 모서리는 최대 32개다.

설계

---

두 가지를 고려해 구현하면 될 것 같다.

• 전화선이 건물의 변과 교차하는 경우
• 전화선이 건물의 꼭지점과 접촉하는 경우

꼭지점과 접촉 판별이 가능하면 꼭지점을 통해 건물을 가로지르는 경우는 생각하지 않아도 될 것 같다.

구현

---

1. 건물 꼭지점 클래스와 입력받기

건물이 사각형으로 정해진게 아니라서 꼭지점 클래스, 꼭지점 클래스의 집합인 건물 클래스를 만들고 사용하려했는데
막상 구현해보니 건물 클래스는 의미 없어서 제외하고 꼭지점 클래스만 사용한다.

public static void main(String[] args) {

	try(BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out))) {
		
		StringTokenizer st = new StringTokenizer(br.readLine()," ");
		
		int xR = Integer.parseInt(st.nextToken());
		int yR = Integer.parseInt(st.nextToken());
		int xJ = Integer.parseInt(st.nextToken());
		int yJ = Integer.parseInt(st.nextToken());
		
		int n = Integer.parseInt(br.readLine());
		int count = 0;
		
		for (int i = 0 ; i < n ; i++) {
			st = new StringTokenizer(br.readLine()," ");
			int length = Integer.parseInt(st.nextToken());
			Vertex[] vertexes = new Vertex[length];
			int j = 0;
			
			while(st.hasMoreTokens()) {
				int x = Integer.parseInt(st.nextToken());
				int y = Integer.parseInt(st.nextToken());
				
				vertexes[j++] = new Vertex(x, y);
			}
			
		}
		
		bw.write(String.valueOf(count));
		bw.flush();
		
	}catch(IOException e) {
		e.printStackTrace();
	}
}

// 건물 꼭지점 클래스
static class Vertex{
	int x;
	int y;
	
	Vertex(int x, int y){
		this.x = x;
		this.y = y;
	}
}

2. 함수와 메인루프

세 점의 방향성을 계산하는 Counter ClockWise 함수와 점이 선분위에 있는지 판단하는 onSegment 함수를 작성.
이후 꼭지점 수만큼 계산한다.

// Counter ClockWise
static long counterClockWise(int x1, int y1, int x2, int y2, int x3, int y3) {
	return (long)(x2 - x1) * (y3 - y1) - (long)(y2 - y1) * (x3 - x1);
}

// 점이 선분위에 있는지 여부
static boolean onSegment(int x1, int y1, int x2, int y2, int x3, int y3) {
	return Math.min(x1, x2) <= x3 && x3 <= Math.max(x1, x2) &&
			Math.min(y1, y2) <= y3 && y3 <= Math.max(y1, y2);
}

// ... 중략 ...

boolean blocked = false;
    			
// 메인루프
for(int k = 0 ; k < length ; k++) {
	
	// 세 점의 방향성을 확인해 선분 교차 확인
	long ab1 = counterClockWise(xR, yR, xJ, yJ, vertexes[k].x, vertexes[k].y);
	long ab2 = counterClockWise(xR, yR, xJ, yJ, vertexes[(k + 1) % length].x, vertexes[(k + 1) % length].y);
	long cd1 = counterClockWise(vertexes[k].x, vertexes[k].y, vertexes[(k + 1) % length].x, vertexes[(k + 1) % length].y, xR, yR);
	long cd2 = counterClockWise(vertexes[k].x, vertexes[k].y, vertexes[(k + 1) % length].x, vertexes[(k + 1) % length].y, xJ, yJ);
	
	if (ab1 * ab2 < 0 && cd1 * cd2 < 0) {
		blocked = true;
		break;
	}
	
	// 꼭지점 접촉 확인
	if ((ab1 == 0 && onSegment(xR, yR, xJ, yJ, vertexes[k].x, vertexes[k].y)) ||
		(ab2 == 0 && onSegment(xR, yR, xJ, yJ, vertexes[(k + 1) % length].x, vertexes[(k + 1) % length].y)) ||
		(cd1 == 0 && onSegment(vertexes[k].x, vertexes[k].y, vertexes[(k + 1) % length].x, vertexes[(k + 1) % length].y, xR, yR)) ||
		(cd2 == 0 && onSegment(vertexes[k].x, vertexes[k].y, vertexes[(k + 1) % length].x, vertexes[(k + 1) % length].y, xJ, yJ))) {
		blocked = true;
		break;
	}
}

if (blocked) count++;

채점

---

반성

---

왜 자꾸 java 제출할때 패키지를 안지워서 오류내는거지
정신차려라 나야

코드 확인

---

Link to GitHub