CodeUp[Q_2710] : 볼록 사각형

1. 문제

https://codeup.kr/problem.php?id=2710

볼록 사각형

[출처 : 코드업(https://codeup.kr/)]

이번에는 4개의 좌표가 주어질때 이 점들이 볼록 사각형인지 오목 사각형인지 확인하는 문제입니다.

다소 어려워 보이지만 두점을 지나는 직선을 구하는 공식으로 구하면 쉽게 구할수 있습니다.

 

---

직선구하는 공식(Y = aX + b)

(x1, y1), (x2, y2)일때

a = (y1 - y2) / (x1 - x2)

b = y1 - ax1 또는 b = y2 - ax2

 

 

2. 풀이방법

STEP 1. 두점이 주어질때 이 점들을 지나는 직선방적식 구하기

STEP 2. 임의의 두 X값을 넣었을때 하나는 양수, 다른 하나는 음수가 나오면 볼록사각형

 

 

3. 해답

#include <stdio.h>

int arr[4][2];
float a, b;

void linear(int n1, int n2) {
	// y = a*x + b식에서 a,b 구하기
	a = (float)(arr[n1][1] - arr[n2][1]) / (float)(arr[n1][0] - arr[n2][0]);
	b = (float)arr[n1][1] - a * (float)arr[n1][0];
}

int check(int n1, int n2) {
	// 주어진 a,b로 볼록인지 오목인지 확인
	float tmp1, tmp2;

	tmp1 = a * (float)arr[n1][0] + b;
	tmp2 = a * (float)arr[n2][0] + b;

	if (tmp1 > (float)arr[n1][1] && tmp2 < (float)arr[n2][1]) return 1;
	else if (tmp1 < (float)arr[n1][1] && tmp2 >(float)arr[n2][1]) return 1;

	return 0;
}

int main() {
	int d1, d2;

	scanf("%d %d", &arr[0][0], &arr[0][1]);
	scanf("%d %d", &arr[1][0], &arr[1][1]);
	scanf("%d %d", &arr[2][0], &arr[2][1]);
	scanf("%d %d", &arr[3][0], &arr[3][1]);

	// 순서대로 주어지지 않아서
	// 모든 경우의수를 확인
	linear(0, 1);
	if (check(2, 3) == 1) {
		linear(2, 3);
		if (check(0, 1) == 1) {
			printf("1");
			return 0;
		}
	}

	linear(0, 2);
	if (check(1, 3) == 1) {
		linear(1, 3);
		if (check(0, 2) == 1) {
			printf("1");
			return 0;
		}
	}

	linear(0, 3);
	if (check(1, 2) == 1) {
		linear(1, 2);
		if (check(0, 3) == 1) {
			printf("1");
			return 0;
		}
	}

	printf("0");

	return 0;
}

 

해당 코드는 제가 직접 작성한 코드이며 참고용으로만 사용하세요.