Comment detail

情報オリンピック2007年度国内予選問題4 (Nested Flatten)
ログインせずに投稿してしまいました。 宜しければ元の投稿は削除して下さい。ご迷惑おかけします。 探したい星座の座標の1番目を基準として、その相対位置で各星の位置を記録したリストを作成します。次に星空の写真の星の位置の基準を順番に変えてリストを作成し、星座のデータと比較します。比較して、探したい星のリストの各星の全てが星空のデータに含まれていたら、星座の基準と星空の基準を差を出力します。これで星空の写真の大きさに影響しない実行速度が得られますが、星の数に比例して遅くなります。
 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
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
using System;
using System.Collections;
using System.Collections.Generic;

class Program {
    static void Main() {
        string input =
@"5
8 5
6 4
4 3
7 10
0 10
10
10 5
2 7
9 7
8 10
10 2
1 2
8 1
6 7
6 0
0 9";
        List<Location> seiza = new List<Location>();
        Location seizaDefault = new Location() { X = -1, Y = -1 };

        List<Location> yozora = new List<Location>();
        Location yozoreDefault = new Location() { X = -1, Y = -1 };
        List<Location> tmpYozora;

        IEnumerator input_ = input.Split(new char[] { '\n' }).GetEnumerator();
        input_.MoveNext();
        input_.MoveNext();

        while(((string)input_.Current).Trim().Split(new char[] { ' ' }).Length != 1) {
            int x, y;
            string[] row = ((string)input_.Current).Trim().Split(new char[] { ' ' });
            x = int.Parse(row[0].Trim());
            y = int.Parse(row[1].Trim());
            if(seizaDefault.Equals(new Location() { X = -1, Y = -1 })) {
                seizaDefault = new Location() { X = x, Y = y };
                seiza.Add(new Location() { X = 0, Y = 0 });
            } else {
                seiza.Add(new Location() { X = x - seizaDefault.X, Y = y - seizaDefault.Y });
            }
            input_.MoveNext();
        }

        input_.MoveNext();

        do {
            int x, y;
            string[] row = ((string)input_.Current).Trim().Split(new char[] { ' ' });
            x = int.Parse(row[0].Trim());
            y = int.Parse(row[1].Trim());

            yozora.Add(new Location() { X = x, Y = y });
        } while(input_.MoveNext());

        foreach(Location defaultStar in yozora) {
            Location Default = defaultStar;
            tmpYozora = new List<Location>();
            foreach(Location star in yozora) {
                tmpYozora.Add(new Location() { X = star.X - Default.X, Y = star.Y - Default.Y });
            }
            if(Hikaku(seiza, tmpYozora)) {
                Console.WriteLine((Default.X - seizaDefault.X) + " " + (Default.Y - seizaDefault.Y));
                break;
            }
        }
        Console.ReadLine();
    }

    static bool Hikaku(List<Location> seiza, List<Location> yozora) {
        foreach(Location star in seiza) {
            if(!yozora.Contains(star)) return false;
        }
        return true;
    }
}

struct Location {
    public int X;
    public int Y;
}

Index

Feed

Other

Link

Pathtraq

loading...