[2628] 종이자르기

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

2628번: 종이자르기

<문제>

선형 자료구조 2개를 만들어서, 각각 {0, n}과 {0, m}으로 초기화한다.

가로와 세로의 순서에 맞게 입력되는 점선 번호를 전부 넣어주고, 정렬한다.

v[i+1]-v[i]의 최대값을 가로에서 한번, 세로에서 한번 찾아서 두 수를 곱해주면 된다.

 

<소스코드>

#include <bits/stdc++.h>
using namespace std;
int n, m, t, ans, cur;
vector<int> v[2];
int main(void) {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cin >> n >> m >> t;
    int i;
    v[0].push_back(0);
    v[1].push_back(0);
    v[0].push_back(m);
    v[1].push_back(n);
    for (i = 0; i < t; i++) {
        int idx, x;
        cin >> idx >> x;
        v[idx].push_back(x);
    }
    sort(v[0].begin(), v[0].end());
    sort(v[1].begin(), v[1].end());
    int S = v[0].size();
    for (i = 0; i + 1 < S; i++) cur = max(v[0][i + 1] - v[0][i], cur);
    ans = cur;
    S = v[1].size();
    cur = 0;
    for (i = 0; i + 1 < S; i++) cur = max(v[1][i + 1] - v[1][i], cur);
    ans *= cur;
    cout << ans;
    return 0;
}