(알고리즘) Geometry Problem(1)

저번 코딩테스트에서 기하문제때매 크게 데인적이 있어,

기하쪽 문제풀이를 해봐야 겠다 생각하다, 이번에 하게되었다.

 

1. 30962 센서

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

30962번: 센서

이 문제가 코테에서 나왔던 문제와 비슷한 문제이다.

먼저 생각해야할 것이 점1(x1, y1)과 점2(x2, y2)사이에 있는 후보 점을 어떻게 추려낼 것이냐가

첫 번째 고민이 될 수 있다.

문제에서 점1과 점2의 각도 사이에 원점(0, 0)에서 거리가 sqrt(w)인 점들을 찾는 것이다.

그렇다면 다음과 같은 식을 쓸 수 있다.

w = (x - 0)^2 + (y - 0)^2

w = x^2 + y^2

sqrt(w) = x + y

그렇다면 x나 y를 1 ~ sqrt(w)로 고정시킨다면(나는 x로 고정했기에 y를 찾는 수식을 씀)

y = sqrt(w) - x

y = sqrt(w - x^2)

다음과 같이 x와 y를 구할 수 있다.

여기서 x^2 + y^2 = w인지를 판별하면 그 점은 후보군에 들 수 있다.

이제 두 번째로 이 점이 거리가 sqrt(w)인 것은 알았고, 점1과 점2의 각도안에 들어오는지를 어떻게 알 수 있을까?

CCW 알고리즘을 사용하는 방법이 있다.

먼저 CCW 알고리즘을 사용하여 점1과 후보점, 후보점과 점2를 CCW로 구한뒤 나온 값을 곱하여 0이하가 나온다면 각도안에 있는 것이다.

왜냐하면 점1과 후보점, 후보점과 점2는 시계방향 혹은 기준점과 일직선 상에 있으야 포함이 되는 것이기 때문이다.

 

(소스코드)

#include <iostream>
#include <cmath>
using namespace std;

int ccw(int x1, int y1, int x2, int y2){
    int k = x1 * y2 - y1 * x2;
    
    if(k < 0) return -1;
    else if(k > 0) return 1;
    else return 0;
}

int main(){
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    int q; cin >> q;
    
    while(q--){
        int x1,y1,x2,y2,w; cin >> x1 >> y1 >> x2 >> y2 >> w;
        
        int dist = (int)sqrt(w);
        int cnt = 0;
        for(int x = 1;x<=dist;x++){
            int y = sqrt(w - x * x);
            if(w == x * x + y * y){
                if(ccw(x1, y1, x, y) * ccw(x2, y2, x, y) <= 0) cnt++;
            }
        }
        cout << cnt << "\n";
    }
}

 

 

2. 25308 방사형 그래프

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

25308번: 방사형 그래프

 

 

먼저 이 문제를 풀려면 총 8개의 점의 좌표를 알아야한다.

일단 4개의 점은 바로 알 수 있다.

a1, a3, a5, a7은 x가 0이거나 y가 0이기에 바로 좌표가 나온다.

그렇다면 나머지 a2, a4, a6, a8은 어떻게 구할 수 있을까?

먼저 문제에 45도 각도로 멀어진다고 되어있다.

그렇기에 직각삼각형을 그릴 수 있다.

이제 삼각함수를 떠올릴 수 있는데,

x좌표는 cos45 = x/a_i,  x = cos45 * a_i

y좌표는  sin45 = y/a_i,  y = sin45 * a_i

이렇게 x좌표와 y좌표를 구할 수 있다.

여기서 1,2,3,4 분면에 따라 -, +를 붙여서 해주면 된다.

 

이제 좌표를 구했으니 구현을 해야하는데, 입력의 모든 경우의 수느 8!이다 그러면 모든 경우의 수를 다 봐보면 된다.

이제 이 그래프가 볼록 다각형인지 판별하기 위해서 위의 문제와 마찬가지로 CCW알고리즘을 이용해

모든 꼭지점을 이루는 점들의 CCW가 시계방향으로 가는지를 판단하면 된다.

 

(소스코드)

#include <iostream>
#include <algorithm>
#include <vector>
#include <cmath>
#define pii pair<double, double>
using namespace std;
const double pi = 3.141592;

bool ccw(pii dot1, pii dot2, pii dot3) {
	double k = (dot2.first - dot1.first) * (dot3.second - dot1.second) - (dot3.first - dot1.first) * (dot2.second - dot1.second);
	if (k < 0) return true;
	else return false;
}

bool check(vector<int> arrs) {
	vector<pii> now(8);
	double k = sin(45.0 * pi / 180);
	now[0] = { 0, arrs[0] };
	now[1] = { k * arrs[1], k * arrs[1] };
	now[2] = { arrs[2], 0 };
	now[3] = { k * arrs[3], -k * arrs[3] };
	now[4] = { 0, -arrs[4] };
	now[5] = { -k * arrs[5], -k * arrs[5] };
	now[6] = { -arrs[6], 0 };
	now[7] = { -k * arrs[7], k * arrs[7] };
	bool checks = false;
	for (int i = 0; i < 8; i++) {
		if (!ccw(now[i], now[(i + 1) % 8], now[(i + 2) % 8])) checks = true;
	}
	return checks;
}

int main() {
	ios::sync_with_stdio(false); cin.tie(NULL);
	vector<int> arr(8);
	vector<int> idx(8);
	for (int i = 0; i < 8; i++) {
		cin >> arr[i];
		idx[i] = i;
	}
	int ans = 0;
	do {
		vector<int> checkarr(8);

		for (int i = 0; i < 8; i++) checkarr[i] = arr[idx[i]];

		if (!check(checkarr)) ans++;
	} while (next_permutation(idx.begin(), idx.end()));

	cout << ans;
	return 0;
}

 

 

오늘은 2문제를 풀었고, 다음으로 선분교차 알고리즘을 공부해보려고 한다.