Algoogle

Algorithm for Programming Contest

JOI 春合宿 2009 Territory

Category: JOI Tag: implementation

Territory

問題概要


ジョイ君が歩いた経路に囲まれる部分の面積の総和を求めよ

解法


経路を右手法で回りながら西に進むときはy座標の大きさを足して, 東に進むときはy座標の大きさを引いていくことで面積の総和を求める.

コード


(Territory.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
42
#include <bits/stdc++.h>
using namespace std;
typedef pair<int,int> pii;
const string dir = "NESW";
const int dx[] = {0,1,0,-1}, dy[] = {-1,0,1,0};

map<pii,int> ps;

void add_edge(int &x, int &y, char c)
{
        int d = dir.find(c);
        ps[pii(x,y)] |= 1<<d;
        x += dx[d]; y += dy[d];
        ps[pii(x,y)] |= 1<<((d+2)%4);
}

int solve()
{
        char c;
        int x = 0, y = 0;
        while(cin>>c, c!='Q') add_edge(x,y,c);
        x = begin(ps)->first.first; y = begin(ps)->first.second;
        int tx = x, ty = y, ans = 0, d = 1;
        do {
                if((ps[pii(x,y)]>>d)&1) {
                        if(d%2) ans += y*(d-2);
                        x += dx[d];
                        y += dy[d];
                        d = (d+3)%4;
                }
                else d = (d+1)%4;
        } while(x != tx or y != ty or d != 1);
        return ans;
}

int main()
{
        cin.tie(0);
        cin.sync_with_stdio(0);
        cout << solve() << endl;
        return 0;
}

Comments