BOJ - 25308 ) 방사형 그래프

---

오목/볼록 다각형을 판단하기위한 알고리즘으로 CCW를 사용한다.

CCW가 잘 설명되어 있는글은 

https://jason9319.tistory.com/358

CCW와 CCW를 이용한 선분 교차 판별

이글을 판단하면 된다. 

 

Z=0인 두 벡터를 연결한다면, 1 > 2 > 3 순서의 ccw값이 ( z=0 인 외적값 )

양수면 반시계방향에 위치에있다

0이면 일직선상에있다 ( 외적으로 만드는 평행사변형의 넓이값이 0이라는뜻)

음수면 시계방향으로 세점이 위치해있다.

를 이용하여, 점들간 ( 3점으로 했는데 모든점으로 확장해도 통과할듯하다 )의 ccw값이 음수이면,

시계방향으로 점들이 배열된다는 뜻이고, 이는 볼록다각형이랑는 말과 동치이다.

 

점의 좌표는 방사형 그래프를 원점으로 두고, 각 꼭지점은 pi/4 이므로 이를 이용하여 각 좌표를 계산할 수 있다.

---

https://www.acmicpc.net/problem/25308

25308번: 방사형 그래프

---

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

class BOJ_25308{
	public static int input[] = new int[8];
	public static int order[] = {0,1,2,3,4,5,6,7};
	public static void main(String[] args) throws IOException {
		BufferedReader br= new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		for(int i=0;i<8;i++) {input[i] = Integer.parseInt(st.nextToken());}
		int answer=0;
		do {

		    boolean isPossible = true;
			for(int i=0;i<8;i++) {
			
				float result_ccw = ccw(
						                   new float[] { (float) - (input[order[i%8]] / Math.sqrt(2)),  (float) (input[order[i%8]] / Math.sqrt(2)) }
					                     , new float[] { (float)   0  ,  (float) (input[order[(i+1)%8]])}
					                     , new float[] { (float)  (input[order[(i+2)%8]] / Math.sqrt(2)),  (float) (input[order[(i+2)%8]] / Math.sqrt(2))}
					                   );
				if(result_ccw >= 0) {
					isPossible =false;
				}
				if(!isPossible) {
					break;
				}
			}
			
			
					
			
			if(isPossible) {
				answer++;
			}
		} while(nextPermutation(order));
		System.out.println(answer);
	}
	

	public static float ccw(float []a, float []b, float []c) {
		// ccw 계산 , 일직선에 올수 없다( 정수이기 때문 )
		return (a[0]*b[1]+b[0]*c[1]+c[0]*a[1])-(b[0]*a[1]+c[0]*b[1]+a[0]*c[1]);
		
	}
	static boolean nextPermutation(int[] arr) {
		
		int i=7;
		while( i>0 && arr[i-1] >= arr[i] ) --i; 
		if(i==0) return false;
		
		int j = 7;
		while(arr[i-1]>=arr[j]) --j;
		
		int temp = order[i-1];
		order[i-1] = order[j];
		order[j] = temp;
		
		int k = 7;
		while(i<k) {
		    temp=order[i];
		    order[i]=order[k];
		    order[k]=temp;
			++i; --k;
		}
		return true;		
	}
}

---