[백준 17611] 직각다각형

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

17611번: 직각다각형

 

 

  꼭짓점의 개수와 좌표가 입력으로 주어지고 해당 꼭짓점들을 순서대로 연결했을 때 만들어지는 직각다각형을 수직 또는 수평으로 지나는 선을 그었을 때 교점의 최대 개수를 출력하는 문제이다.

 

직각다각형이라는 조건이 있으므로 이웃하는 두 꼭짓점의 x좌표, y좌표 중 하나는 무조건 같다. 따라서,

• 이웃하는 두 꼭짓점의 x좌표가 같을 경우, 두 점의 y좌표 중 작은 값에서 큰 값까지 반복문을 돌리면서 해당 y값을 인덱스로 가지는 배열을 원소를 1씩 더해준다.
• 이웃하는 두 꼭짓점의 y좌표가 같을 경우, x좌표에 대해 똑같이 반복해준다.

  이렇게 하면 x와 y값을 각각 인덱스로 가지는 두 배열의 원소에 해당 좌표에 수직 또는 수평선을 그었을 때 생기는 교점의 개수가 저장된다. 이중에서 가장 큰 값을 출력한다.

 

 

  하지만 위와 같이 풀면 틀린다.  수직,수평선은 정수좌표에만 존재하는 것이 아니라는 사실을 간과했다. 수직, 수평선은 다각형의 어떠한 선분과도 겹치면 안 된다는 조건 때문에 반복문의 범위를 두 꼭짓점의 좌표는 포함하지 않게 설정했다. 여기서 문제가 생긴 것이다. 예를 들어 아래와 같은 직각다각형의 경우 위의 풀이로는 출력값이 4인데 정답은 6이기 때문이다. 이 때문에 위의 풀이 방법은 적용할 수 없다.

 

  이를 해결하기 위해 입력받은 좌표값에 2를 곱하고 배열의 크기도 2배 늘렸다. 문제 조건이 좌표가 양수로 100만이었기 때문에 문제없었다. 이렇게 하니 수직, 수평선이 정수좌표가 아닌 경우에 대해서도 카운트를 할 수 있었다.

즉, 입력값이 (1,5), (3,5)인 경우 수직선을 x값이 1.5 , 2, 2.5인 위치에 그을 수 있다고 가정을 한 것이다. 이를 정수로 표현하기 위해 2를 곱하였다.

 

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

int xAmount[2000001];
int yAmount[2000001];

void yCounting(int y1, int y2) {
	for (int j = min(y1, y2) + 1; j < max(y1, y2); j++)
		yAmount[j]++;
}

void xCounting(int x1, int x2) {
	for (int j = min(x1, x2) + 1; j < max(x1, x2); j++)
		xAmount[j]++;
}
int main() {
	int n;
	int x0, y0;
	int xTmp, yTmp;
	int x, y;
	int ans = 0;
	cin >> n;
	
	for (int i = 0; i < n; i++) {
		cin >> x >> y;
		x *= 2, y *= 2;
		x += 1000000;
		y += 1000000;
		if (i == 0) {
			x0 = x, xTmp = x;
			y0 = y, yTmp = y;
			continue;
		}
		if (xTmp == x)
			yCounting(yTmp, y);
		
		else if (yTmp == y)
			xCounting(xTmp, x);
		
		xTmp = x, yTmp = y;
	}

	if (xTmp == x0)
		yCounting(yTmp, y0);
	
	else if (yTmp == y0)
		xCounting(xTmp, x0);

	for (int i = 1; i < 2000001; i++)
		ans = max(ans, max(xAmount[i], yAmount[i]));
	
	cout << ans;
}

 

다행히 한 번에 통과했다.