백준15923 욱제는 건축왕이야!!

작성일 | In

문제 링크

  • http://icpc.me/15923

문제 출처

  • 제2회 천하제일 코딩대회 H번

시간복잡도

  • O(n)

풀이

점이 주어지는 순서대로 이어서 건물 설계도를 그릴 수 있습니다.
해당 건물의 둘레는 주어지는 순서대로 거리를 구해서 모두 더하면 됩니다.

여담 : 가끔 대회 당시에 convex 라는 단어를 보자마자 graham’s scan을 구현했던 저를 자책하곤 합니다.

전체 코드

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
#include <bits/stdc++.h>
using namespace std;

typedef pair<int, int> p;
vector<p> arr;

int main(){
	int sum = 0;
	int n; scanf("%d", &n);
	for(int i=0; i<n; i++){
		int x, y; scanf("%d %d", &x, &y);
		arr.push_back(make_pair(x, y));
	}

	int xx, yy;
	for(int i=0; i<n-1; i++){
		xx = arr[i+1].first - arr[i].first;
		yy = arr[i+1].second - arr[i].second;
		sum += (int)sqrt(xx*xx + yy*yy);
	}
	xx = arr[n-1].first - arr[0].first;
	yy = arr[n-1].second - arr[0].second;
	sum += (int)sqrt(xx*xx + yy*yy);
	printf("%d", sum);
}