# [Silver V] 유물 발굴 [문제 링크](https://www.acmicpc.net/problem/32344) ## 문제 설명 <p>홍익대학교 운동장은 $R$행 $C$열 크기의 격자 모양이다. 이런 홍익대학교 운동장에서 학계를 뒤흔들만한 유물의 조각들이 발견되었다. 하지만 한 번에 여러 유물을 발굴하는 것은 불가능하다. 따라서, 유물의 예상 크기를 조사해서 예상 크기가 가장 큰 유물을 먼저 발굴하려고 한다. 만약 그런 유물이 여러 개라면, 번호가 가장 작은 것을 먼저 발굴하려고 한다.</p> <p>조각은 $1 \times 1$ 크기이고, 같은 위치에 여러 조각이 존재할 수 있다. 유물의 예상 크기는 해당 유물의 조각들을 한번에 묶을 수 있는 가장 작은 직사각형의 크기이다. 직사각형의 모든 변은 운동장과 평행해야 한다.</p> <p>가장 먼저 발굴하는 유물의 번호와 예상 크기를 알아내보자!</p> ## 입력 <p>첫째 줄에 홍익대학교 운동장의 세로 길이를 나타내는 정수 $R$, 가로 길이를 나타내는 정수 $C$가 공백으로 구분되어 주어진다. $(1 \leq R, C \leq 100\,000)$</p> <p>둘째 줄에 조각의 개수 정수 $N$이 주어진다. $(1 \leq N \leq 100\,000)$</p> <p>셋째 줄부터 $N$개의 줄에 걸쳐 정수 $a_i$, $v_i$, $h_i$가 공백으로 구분되어 주어진다. $(1 \leq a_i \leq N;$ $1 \leq v_i \leq R; 1 \leq h_i \leq C)$ 이는 $a_i$번 유물의 조각이 $v_i$행 $h_i$열에 존재함을 의미한다.</p> ## 출력 <p>첫째 줄에 가장 먼저 발굴하는 유물의 번호와 예상 크기를 공백으로 구분하여 출력한다.</p> ## 풀이 각 유물마다 최대 최소 x, y를 저장하며 크기를 계산하면 됩니다. ``` c++ #include<bits/stdc++.h> using namespace std; typedef long long ll; const int MAX = 100'001; ll maxH[MAX], minH[MAX], maxV[MAX], minV[MAX]; int main() { ios::sync_with_stdio(0); cin.tie(0); int r, c, n; cin >> r >> c >> n; int idx=0; ll maxSize=0; fill(minH, minH+MAX, MAX); fill(minV, minV+MAX, MAX); while(n--) { ll a, v, h; cin >> a >> v >> h; minH[a] = min(minH[a], h); maxH[a] = max(maxH[a], h); minV[a] = min(minV[a], v); maxV[a] = max(maxV[a], v); ll size = (maxH[a]-minH[a]+1)*(maxV[a]-minV[a]+1); if(maxSize<size || maxSize==size && idx>a) { maxSize = size; idx=a; } } cout << idx << ' ' << maxSize; } ```