[백준 2538] 모눈종이 자르기

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

2538번: 모눈종이 자르기

 

완전 구현문제였다. 처음에는 조각을 판정하고 각 조각의 칸을 dfs로 돌며 모눈종이의 경계선 또는 다각형의 둘레에 접하는 수만큼 카운트하여 둘레를 직접 계산하는 것을 구현했는데 입력 조건이 가로 세로 길이가 20만이어서 시간초과가 난다는 사실을 깨달았다. 그래서 입력받은 다각형의 꼭짓점 위치를 바탕으로 조각의 둘레를 계산하는 방법으로 바꿨다.

 

---

문제에서, 다각형의 꼭짓점을 입력받을 때 시계반대방향으로 입력받는다고 했기 때문에 연속하는 두 꼭짓점의 좌표를 통해 조각을 나눌 수 있다.

 

1. 연속하는 두 꼭짓점이 모눈종이의 테두리에 위치하는지 확인하여 조각을 나누고,

 

2. start, end 변수를 통해 꼭짓점을 이동한다.

 

3. 각 조각의 시작점과 끝점이 모눈종이의 테두리에 위치한다는 사실을 통해 조각의 둘레 중 다각형의 변에 위치하는 부분들 판별하여 더해주고,

 

4. 각 조각의 시작점부터 끝점의 좌표를 이용하여 조각의 둘레 중 모눈종이의 테두리에 위치하는 부분을 찾아 더해준다.

 

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

struct point {
	int x, y;
};
int xLen, yLen;
int n;
point pos[500002];
long long sum, ans_cnt, ans_max;

bool is_Xborder(point p1, point p2) {
	return (p1.x == p2.x && (p1.x == 0 || p1.x == xLen));
}

bool is_Yborder(point p1, point p2) {
	return (p1.y == p2.y && (p1.y == 0 || p1.y == yLen));
}

long long dist(point p1, point p2) {
	return abs(p1.x - p2.x) + abs(p1.y - p2.y);
}

long long length(int start, int end) {
	point p1 = pos[start];
	point p2 = pos[end];
	long long total = 0;
	while (true) {
		if (is_Yborder(p1, p2) || is_Xborder(p1, p2)) {
			return total += dist(p1, p2);
		}
		if (p1.y == 0 && p1.x != xLen) {
            total += (xLen - p1.x);
			p1.x = xLen;
		}
		else if (p1.x == 0 && p1.y != 0) {
            total += p1.y;
			p1.y = 0;
		}
		else if (p1.x != 0 && p1.y == yLen) {
            total += p1.x;
			p1.x = 0;
		}
		else if (p1.x == xLen && p1.y != yLen) {
            total += (yLen - p1.y);
			p1.y = yLen;
		}
	}
}

int main() {
	cin >> xLen >> yLen;
	cin >> n;
	for (int i = 0; i < n; i++) {
		cin >> pos[i].x >> pos[i].y;
	}
	pos[n].x = pos[0].x;
	pos[n].y = pos[0].y;
	int start = 1, end;
	bool chk = false;
    //조각의 시작점 추출.
	for (int i = 0; i < n; i++) {
		if (is_Xborder(pos[i], pos[i + 1]) || is_Yborder(pos[i], pos[i + 1])) {
			chk = true;
            start = (i + 1) % n;
			break;
		}
	}
    //조각이 하나인 경우(구멍).
	if (!chk) {
		ans_cnt = 1;
		ans_max = xLen * 2 + yLen * 2;
		for (int i = 0; i < n; i++) {
			ans_max += dist(pos[i], pos[i + 1]);
		}
		cout << ans_cnt << " " << ans_max;
		return 0;
	}

    end = start;
	for (int i = 0; i < n; i++) {
		if (is_Xborder(pos[end], pos[end + 1]) || is_Yborder(pos[end], pos[end + 1])) {
			if (!chk) {
				ans_cnt++;
				sum += length(start, end);
				ans_max = max(ans_max, sum);
				sum = 0;
				chk = 1;
			}
            start = (end + 1) % n;
		}
		else {
			sum += dist(pos[end], pos[end + 1]);
            chk = false;
		}
        end = (end + 1) % n;
	}
	cout << ans_cnt << " " << ans_max;
}