Algoogle

Algorithm for Programming Contest

JOI 春合宿 2008 Origami

Category: JOI Tag: compress

Origami

問題概要


折り紙を重ねておいていくので, 一番かぶっている厚さとその面積を求めよ

解法


座標圧縮っぽくやる.
折り紙の幅と高さはそれぞれ高々20なので全ての位置をmapでカウントしても問題ない.

コード


(Origami.cpp) download
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
40
41
#include <bits/stdc++.h>
using namespace std;

int n, h, w;
map<pair<int,int>, int> f;

void solve()
{

        int p, q, r, s, m = 0, area = 0;
        for (int i = 0; i < n; i++) {
                cin >> p >> q >> r >> s;
                p--; q--;
                for (int y = q; y < s; y++) {
                        for (int x = p; x < r; x++) {
                                int t = ++f[pair<int,int>(x,y)];
                                if(t > m) {
                                        m = t;
                                        area = 0;
                                }
                                if(t == m) area++;
                        }
                }
        }
        cout << m << endl;
        cout << area << endl;
}

void input()
{
        cin >> n >> w >> h;
}

int main()
{
        cin.tie(0);
        cin.sync_with_stdio(0);
        input();
        solve();
        return 0;
}

Comments