백준17611 직각다각형

작성일 | In

문제 출처

  • 2019 KOI 1차 중등부 2번

사용 알고리즘

  • Prefix-Sum

시간복잡도

  • O(N)

풀이

sumX[i]를 x좌표가 i인 곳을 지나는 가로 방향 변의 개수라고 정의합시다.
sumY[i]를 y좌표가 i인 곳을 지나는 세로 방향 변의 개수라고 정의합시다.

가로 방향 변이 시작하는 지점을 x1, 끝나는 지점을 x2라고 하면 sumX[x1]을 1 증가시키고 sumX[x2]를 1 감소시킨 뒤, 누적합을 구해주면 원하는 sumX를 구할 수 있습니다.
같은 방법으로, 세로 방향 변이 시작하는 지점을 y1, 끝나는 지점을 y2라고 하면 sumY[y1]을 1 증가시키고 sumY[y2]를 1 감소시킨 뒤, 누적합을 구해주면 원하는 sumY를 구할 수 있습니다.

sumX의 최댓값과 sumY의 최댓값 중 더 큰 값이 정답이 됩니다.

전체 코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
#include <bits/stdc++.h>
#define x first
#define y second
using namespace std;

typedef pair<int, int> p;

int sumX[1010101];
int sumY[1010101];
vector<p> v;

int main(){
	ios_base::sync_with_stdio(0); cin.tie(0);
	int n; cin >> n; v.resize(n);
	for(int i=0; i<n; i++){
		cin >> v[i].x >> v[i].y;
		v[i].x += 500005;
		v[i].y += 500005;
	}

	for(int i=0; i<n; i++){
		p now = v[i], nxt = v[(i+1)%n];
		if(now.y == nxt.y){
			sumX[min(now.x, nxt.x)]++;
			sumX[max(now.x, nxt.x)]--;
		}else{
			sumY[min(now.y, nxt.y)]++;
			sumY[max(now.y, nxt.y)]--;
		}
	}

	for(int i=1; i<1010101; i++){
		sumX[i] += sumX[i-1];
		sumY[i] += sumY[i-1];
	}

	int ans = max(*max_element(sumX, sumX+1010101), *max_element(sumY, sumY+1010101));
	cout << ans << "\n";
}