Yukicoder No.92 逃走経路

http://yukicoder.me/problems/149

考察

dfsで行けるとこ全部行ったらTLEした．戻ることも考えられるので，状態数がすごいことになることがわかっていなかった．よくよく考えると，i回目の移動でいる場所としてはmaxでNなので，行ける場所をもって最後まで残った場所を答える．

Code

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
87
88
89
90

#include <iostream>
#include <vector>
#include <string>
#include <cstring>
#include <algorithm>
#include <sstream>
#include <map>
#include <set>

#define REP(i,k,n) for(int i=k;i<n;i++)
#define rep(i,n) for(int i=0;i<n;i++)
#define INF 1<<30
#define pb push_back
#define mp make_pair

using namespace std;
typedef long long ll;
typedef pair<int,int> P;

struct edge {
    int from,to;
    int cost;

    edge(int t,int c) : to(t),cost(c) {}
    edge(int f,int t,int c) : from(f),to(t),cost(c) {}

    bool operator<(const edge &e) const {
        return cost < e.cost;
    }
};

vector<int> v;
int n,m,k;

int main() {
    cin >> n >> m >> k;

    map<int,vector<edge> > edges;
    rep(i,m) {
        int a,b,c;
        cin >> a >> b >> c;

        a--;
        b--;

        edges[c].push_back(edge(a,b,c));
        edges[c].push_back(edge(b,a,c));
    }

    v.resize(k);
    rep(i,k) cin >> v[i];

    vector<int> ans(n);
    rep(i,n) ans[i] = i;
    rep(i,k) {
        bool used[105];
        memset(used,0,sizeof(used));

        rep(j,ans.size()) {
            used[ans[j]] = true;
        }

        vector<edge> es = edges[v[i]];
        vector<int> temp;
        rep(j,es.size()) {
            int f = es[j].from;
            int t = es[j].to;

            if(used[f]) {
                temp.push_back(t);
            }
        }

        sort(temp.begin(),temp.end());
        temp.erase(unique(temp.begin(),temp.end()),temp.end());

        ans.resize(temp.size());
        rep(j,temp.size()) ans[j] = temp[j];
    }

    sort(ans.begin(),ans.end());
    cout << ans.size() << endl;
    rep(i,ans.size()) {
        cout << ans[i] + 1;
        if(i == ans.size()-1) cout << endl;
        else cout << " ";
    }

    return 0;
}
Sep 3rd, 2015
yukicoder, グラフ, 星2

Yukicoder No.78 クジ付アイスバー

http://yukicoder.me/problems/152

考察

以下の通りに場合分けして考えた．
- n > kの時，食べる予定のアイスバーの分回せばいい(最大50)．
- そうではない時，まず1箱分回した時に，いくつ当たりが残るかを調べる．
- ここで残った当たりが1箱勝った数と同じ場合はそれが答え(目標のkまで最初の1箱分だけでいける)
- 同じでなかった時は，全部開ける箱と，買い終わってアイスが残る箱に分けて考える

まずは愚直にやってTLEをして，–と++を間違えてWAを生やした

Code

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

#include <iostream>
#include <vector>
#include <string>
#include <cstring>
#include <algorithm>
#include <sstream>
#include <map>
#include <set>

#define REP(i,k,n) for(int i=k;i<n;i++)
#define rep(i,n) for(int i=0;i<n;i++)
#define INF 1<<30
#define pb push_back
#define mp make_pair

using namespace std;
typedef long long ll;
typedef pair<int,int> P;

int main() {
    int n,k;
    cin >> n >> k;
    string s;
    cin >> s;

    vector<int> v(n);
    rep(i,n) v[i] = s[i] - '0';

    if(n > k) {
        int ans = 0, cnt = 0;
        rep(i,k) {
            if(cnt > 0) cnt--;
            else ans++;

            cnt += v[i];
        }

        cout << ans << endl;
    } else {
        int res = 0, cnt = 0;
        rep(i,n) {
            if(cnt > 0) cnt--;
            else res++;

            cnt += v[i];
        }

        if(cnt >= res) {
            cout << res << endl;
        } else {
            int m = 0;
            int ans = 0, q = 0;
            while(m + n <= k) {
                m += n;
                if(q >= res) {
                    q -= res;
                    q += cnt;
                } else {
                    ans += res - q;
                    q = cnt;
                }
            }

            rep(i,k%n) {
                if(q > 0) q--;
                else ans++;

                q += v[i];
            }

            cout << ans << endl;
        }

    }
    return 0;
}
Sep 3rd, 2015
yukicoder, 星2

Yukicoder No.77 レンガのピラミッド

http://yukicoder.me/problems/186

考察

移動とは

任意の列の一番上にある1つのレンガを持ち，別の列に移動するか，もしくは捨て置き場に移動すること．

なので，ピラミッドの長さを決めたら，それに対応する長さとのdiffを取る．もし超えている部分のほうが大きくても捨て置き場に置けばよいので，長さを決め打ちすれば，その長さにするための移動数が求まる．ピラミッドの長さはNよりも大きくてもよいので(特に考えず出してWAを生やした)，十分な回数まで調べた．

Code

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

#include <iostream>
#include <vector>
#include <string>
#include <cstring>
#include <algorithm>
#include <sstream>
#include <map>
#include <set>

#define REP(i,k,n) for(int i=k;i<n;i++)
#define rep(i,n) for(int i=0;i<n;i++)
#define INF 1<<30
#define pb push_back
#define mp make_pair

using namespace std;
typedef long long ll;
typedef pair<int,int> P;

vector<int> init(int n) {
    vector<int> ret;
    rep(i,n/2) {
        ret.push_back(i+1);
    }
    ret.push_back(n/2+1);
    for(int i=n/2; i>0; i--) {
        ret.push_back(i);
    }
    return ret;
}

int main() {
    int n;
    cin >> n;

    vector<int> v(1005);
    rep(i,n) cin >> v[i];

    int ans = INF;

    REP(size,1,1005) {
        if(size % 2 == 0) continue;
        vector<int> t = init(size);

        rep(i,n) {
            int a = 0, b = 0;

            rep(j,i) a += v[j];

            REP(j,i,size) {
                if(v[j] > t[j-i]) {
                    a += v[j] - t[j-i];
                }
                if(v[j] < t[j-i]) {
                    b += t[j-i] - v[j];
                }
            }

            REP(j,size,n) a += v[j];

            if(a >= b) {
                ans = min(ans,a);
            }
        }
    }

    cout << ans << endl;

    return 0;
}
Sep 3rd, 2015
yukicoder, 全探索, 星2

Yukicoder No.55 正方形を描くだけの簡単なお仕事です

http://yukicoder.me/problems/83

Sample1 Sample2 この3点では正方形が出来ない Sample3 Sample4

考察

3点が与えられ，正方形となるもう1点を答えるのだが，正方形がx軸，y軸に平行でなくてもいい．3点の中で最も2点間の距離が長いものを線分として，もう1点をその線分に対して対象な点を求めた．

サンプル3を考える． 一番長い線分を見つける． この線分に対し，対象な点を取る． 正方形の完成．

このままではひし型も作れてしまうので，与えられた3点によって出来る三角形が二等辺三角形かつ，短い辺のが，長い辺となる時のみ行う．

Code

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
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173

#include <iostream>
#include <vector>
#include <string>
#include <cstring>
#include <algorithm>
#include <sstream>
#include <map>
#include <set>
#include <cmath>

#define REP(i,k,n) for(int i=k;i<n;i++)
#define rep(i,n) for(int i=0;i<n;i++)
#define INF 1<<30
#define pb push_back
#define mp make_pair
#define EPS 1e-8
#define equals(a,b) fabs((a) - (b)) < EPS

using namespace std;
typedef long long ll;
typedef pair<int,int> P;

struct Point {
    double x, y;

    Point(double x=0, double y=0) : x(x), y(y) {}

    Point operator+(const Point &o) const { return Point(x+o.x, y+o.y); }

    Point operator-(const Point &o) const { return Point(x-o.x, y-o.y); }

    Point operator*(const double m) const { return Point(x*m, y*m); }

    Point operator/(const double d) const { return Point(x/d, y/d); }

    bool operator<(const Point &o) const { return x != o.x ? x < o.x : y < o.y; }

    bool operator==(const Point &o) const { return fabs(x-o.x) < EPS && fabs(y-o.y) < EPS; }

    double cross(const Point &o) const { return x * o.y - y * o.x; }

    double dot(const Point &o) const { return x * o.x + y * o.y; }

    double atan() const { return atan2(y, x); }

    double norm() const { return sqrt(dot(*this)); }

    double distance(const Point &o) const { return (o - (*this)).norm(); }

    double area(const Point &a,const Point &b) {
        Point p = a - (*this), p2 = b - (*this);
        return p.cross(p2);
    }

    double area_abs(const Point &a,const Point &b) const {
        Point p = a - (*this), p2 = b - (*this);
        return fabs(p.cross(p2)) / 2.0;
    }  

    //線分abが自身に含まれているのかどうか判断する
    int between(const Point &a,const Point &b) {
        if(area(a,b) != 0) return 0;

        if(a.x != b.x)  return ((a.x <= x) && (x <= b.x) || (a.x >= x) && (x >= b.x));
        else return ((a.y <= y) && (y <= b.y) || (a.y >= y) && (y >= b.y));
    }

    double distance_seg(const Point& a,const Point& b) {
        if((b-a).dot(*this-a) < EPS) {
            return (*this-a).norm();
        }
        if((a-b).dot(*this-b) < EPS) {
            return (*this-b).norm();
        }
        return abs((b-a).cross(*this-a)) / (b-a).norm();
    }

    bool hitPolygon(const Point& a,const Point& b,const Point& c) {
        double t = (b-a).cross(*this-b);
        double t2 = (c-b).cross(*this-c);
        double t3 = (a-c).cross(*this-a);   

        if((t > 0 && t2 > 0 && t3 > 0) || ( t < 0 && t2 < 0 && t3 < 0)) {
            return true;
        }

        return false;
    }
};

struct Seg {
    Point a,b;

    Seg (Point a, Point b) : a(a),b(b) {}

    bool isOrthogonal(Seg &s) { return equals((b - a).dot(s.b - s.a),0.0); }

    bool isParallel(Seg &s) { return equals((b-a).cross(s.b - s.a),0.0); }

    bool isIntersect(Seg &s) {
        if(s.a.between(a,b) || s.b.between(a,b) || a.between(s.a,s.b) || b.between(s.a,s.b)) {
            return true;
        }
        return ((a-b).cross(s.a-a) * (a-b).cross(s.b-a) < EPS) && ((s.b-s.a).cross(a-s.a)*(s.b-s.a).cross(b-s.a) < EPS);
    }

    bool distance(Seg &s) {
        if((*this).isIntersect(s)) return 0.0;

        return min(min(a.distance_seg(s.a,s.b),b.distance_seg(s.a,s.b)),min(s.a.distance_seg(a,b),s.b.distance_seg(a,b)));
    }

    Point getCrossPoint(Seg &s) {
        Point p = s.b - s.a;
        double d = abs(p.cross(a-s.a));
        double d2 = abs(p.cross(b-s.a));

        double t = d / (d+d2);
        return a + (b-a)*t;
    }

    Point project(Point &p) {
        Point base = b - a;
        double t = base.dot(p-a) / base.dot(base);
        return a + base * t;
    }

    Point reflect(Point &p) {
        return p + (project(p) - p) * 2.0;
    }
};

int main() {
    vector<Point> v(3);
    set<int> id;
    rep(i,3) {
        cin >> v[i].x >> v[i].y;
        id.insert(i);
    }

    set<double> st;
    double len = 0, d = INF;
    rep(i,3) {
        int j = (i+1) % 3;
        double dist = v[i].distance(v[j]);
        len = max(len, dist);
        d = min(d, dist);
        st.insert(dist);
    }

    if(st.size() == 2 && equals(2*d*d,len*len)) {
        int s = 0, t = 0;
        rep(i,3) {
            int j = (i+1) % 3;
            if(len == v[i].distance(v[j])) {
                id.erase(i);
                id.erase(j);
                s = i;
                t = j;
                break;
            }
        }

        Seg seg(v[s],v[t]);
        Point p = seg.reflect(v[*(id.begin())]);
        cout << (int)p.x << " " << (int)p.y << endl;

    } else {
        cout << -1 << endl;
    }

    return 0;
}
Sep 3rd, 2015
yukicoder, 幾何, 星2

Yukicoder No.45 回転寿司

http://yukicoder.me/problems/78

考察

動的計画法で解く．[i][0]をi番目を取らない，[i][1]をi番目を取るとして，dp[i][j]をi番目までの最大値とする．dp[i][0] = max(i-1番目を取った，i-2番目を取った)，dp[i][1] = max(i-1番目を取らない+i番目の価値，i-2番目を取った+i番目の価値)で求める．

Code

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 <iostream>
#include <vector>
#include <string>
#include <cstring>
#include <algorithm>
#include <sstream>
#include <map>
#include <set>

#define REP(i,k,n) for(int i=k;i<n;i++)
#define rep(i,n) for(int i=0;i<n;i++)
#define INF 1<<30
#define pb push_back
#define mp make_pair

using namespace std;
typedef long long ll;
typedef pair<int,int> P;

int main() {
    int n;
    cin >> n;

    vector<int> v(n);
    rep(i,n) cin >> v[i];

    int dp[1005][2];
    memset(dp,0,sizeof(dp));

    dp[0][1] = v[0];
    dp[1][0] = v[0];
    dp[1][1] = v[1];

    REP(i,2,n) {
        dp[i][0] = max(dp[i-1][1],dp[i-2][1]);
        dp[i][1] = max(dp[i-1][0] + v[i],dp[i-2][1] + v[i]);
    }

    cout << max(dp[n-1][0],dp[n-1][1]) << endl;

    return 0;
}
Sep 3rd, 2015
yukicoder, 動的計画法, 星2

Yukicoder No.44 DPなすごろく

http://yukicoder.me/problems/76

考察

1または2前に進むことが出来るので，i+2番目にマスに訪れるにはi番目のマス，またはi+1番目のマスから来るしかない．よって

が成り立つ．フィボナッチ階段を同じ考えである．

Code

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

#include <iostream>
#include <vector>
#include <string>
#include <cstring>
#include <algorithm>
#include <sstream>
#include <map>
#include <set>

#define REP(i,k,n) for(int i=k;i<n;i++)
#define rep(i,n) for(int i=0;i<n;i++)
#define INF 1<<30
#define pb push_back
#define mp make_pair

using namespace std;
typedef long long ll;
typedef pair<int,int> P;

int main() {
    int n;
    cin >> n;

    vector<ll> dp(55);
    dp[0] = 1;
    dp[1] = 1;

    rep(i,n-1) {
        dp[i+2] = dp[i] + dp[i+1];
    }

    cout << dp[n] << endl;

    return 0;
}
Sep 3rd, 2015
yukicoder, 動的計画法, 星2

Yukicoder No.43 野球の試合

http://yukicoder.me/problems/8

考察

0番目のチームに"-“がある場合は必ず，勝ちにする．それ以外の場合はより勝っているチームが負け，負けているチームが勝つようにする，という貪欲は上手くいきそうにない．Nが最大6なので，全てが”-“だとしても状態数は218．よって全ての状態を列挙して，最大で何位になれるかを見る．

Code

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
87
88
89
90
91
92
93
94
95
96
97
98

#include <iostream>
#include <vector>
#include <string>
#include <cstring>
#include <algorithm>
#include <sstream>
#include <map>
#include <set>

#define REP(i,k,n) for(int i=k;i<n;i++)
#define rep(i,n) for(int i=0;i<n;i++)
#define INF 1<<30
#define pb push_back
#define mp make_pair

using namespace std;
typedef long long ll;
typedef pair<int,int> P;

int main() {
    int n;
    cin >> n;

    vector<string> v(n);
    rep(i,n) cin >> v[i];

    vector<int> cnt(n);

    rep(i,n) {
        rep(j,n) {
            if(v[i][j] == '#') continue;
            if(v[i][j] == 'o') cnt[i]++;
        }
    }

    set<P> st;
    rep(i,n) {
        rep(j,n) {
            if(v[i][j] == '-') {
                int s = i, t = j;
                if(s > t) swap(s,t);

                st.insert(P(s,t));
            }
        }
    }

    int ans = n;
    int m = st.size();
    if(m == 0) {
        int val = cnt[0];

        sort(cnt.begin(),cnt.end());
        cnt.erase(unique(cnt.begin(),cnt.end()),cnt.end());
        reverse(cnt.begin(),cnt.end());

        rep(i,cnt.size()) {
            if(val == cnt[i]) {
                ans = i;
                break;
            }
        }
    } else {

        vector<P> v2(st.begin(), st.end());

        rep(i,1<<m) {
            vector<int> res(cnt.begin(), cnt.end());
            rep(j,m) {
                P p = v2[j];
                if(i & (1<<j)) {
                    res[p.first]++;
                } else {
                    res[p.second]++;
                }
            }

            int val = res[0];
            sort(res.begin(),res.end());
            res.erase(unique(res.begin(),res.end()),res.end());
            reverse(res.begin(),res.end());

            int id = 0;
            rep(j,res.size()) {
                if(res[j] == val) {
                    id = j;
                    break;
                }
            }

            ans = min(ans,id);
        }
    }

    cout << ans + 1 << endl;

    return 0;
}
Sep 3rd, 2015
yukicoder, 全探索, 星2

Yukicoder No.17 2つの地点に泊まりたい

http://yukicoder.me/problems/61

考察

nが50と小さいので，0とn-1以外の2つの地点(i,j)を列挙する．0~i，i~j，j~n-1の最短距離，i，jの滞在コストの和の最小値を求める．それぞれの地点からのdijkstraをやったが最初にwarshall_floydをしたほうがスマートに書けそう．

Code

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
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105

#include <iostream>
#include <vector>
#include <string>
#include <cstring>
#include <algorithm>
#include <sstream>
#include <map>
#include <set>
#include <queue>

#define REP(i,k,n) for(int i=k;i<n;i++)
#define rep(i,n) for(int i=0;i<n;i++)
#define INF 1<<30
#define pb push_back
#define mp make_pair

using namespace std;
typedef long long ll;
typedef pair<int,int> P;

struct edge {
    int from,to;
    int cost;

    edge(int t,int c) : to(t),cost(c) {}
    edge(int f,int t,int c) : from(f),to(t),cost(c) {}

    bool operator<(const edge &e) const {
        return cost < e.cost;
    }
};

vector<edge> G[55];
int d[55];

void dijkstra(int s,int n) {
    priority_queue<P,vector<P>,greater<P> > que;
    fill(d,d+n,INF);

    d[s] = 0;
    que.push(P(0,s));

    while(que.size()) {
        P p = que.top();
        que.pop();

        int v = p.second;
        if(d[v] < p.first) continue;

        rep(i,G[v].size()) {
            edge e = G[v][i];
            if(d[e.to] > d[v] + e.cost) {
                d[e.to] = d[v] + e.cost;
                que.push(P(d[e.to],e.to));
            }
        }
    }
}

int main() {
    int n;
    cin >> n;

    vector<int> w(n);
    rep(i,n) cin >> w[i];

    int m;
    cin >> m;

    rep(i,m) {
        int a,b,c;
        cin >> a >> b >> c;

        G[a].push_back(edge(b,c));
        G[b].push_back(edge(a,c));
    }

    int ans = INF;
    REP(i,1,n-1) {
        REP(j,1,n-1) {
            if(i == j) continue;
            int cost = 0;

            dijkstra(0,n);
            if(d[i] == INF) continue;
            cost += d[i];

            dijkstra(i,n);
            if(d[j] == INF) continue;
            cost += d[j];

            dijkstra(j,n);
            if(d[n-1] == INF) continue;
            cost += d[n-1];

            cost += w[i] + w[j];

            ans = min(ans,cost);
        }
    }

    cout << ans << endl;

    return 0;
}
Sep 3rd, 2015
yukicoder, 星2

Hide-and-Seek Supporting System

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0129

サンプル1

円に接してる場合は，Safe判定となる．

考察

円の中心と，線分の関係を見る．Dangerの場合は線分の端点両方が円内包されていない，かつ円の中心と線分の距離が円の半径よりも小さい時である．前回，この問題を取り組んだ時はWAを連発したが，今回はACすることが出来た．

Code

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
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183

#include <iostream>
#include <vector>
#include <string>
#include <cstring>
#include <algorithm>
#include <sstream>
#include <map>
#include <set>
#include <cmath>

#define REP(i,k,n) for(int i=k;i<n;i++)
#define rep(i,n) for(int i=0;i<n;i++)
#define INF 1<<30
#define pb push_back
#define mp make_pair
#define EPS 1e-8
#define equals(a,b) fabs((a) - (b)) < EPS

using namespace std;
typedef long long ll;
typedef pair<int,int> P;

struct Point {
    double x, y;

    Point(double x=0, double y=0) : x(x), y(y) {}

    Point operator+(const Point &o) const { return Point(x+o.x, y+o.y); }

    Point operator-(const Point &o) const { return Point(x-o.x, y-o.y); }

    Point operator*(const double m) const { return Point(x*m, y*m); }

    Point operator/(const double d) const { return Point(x/d, y/d); }

    bool operator<(const Point &o) const { return x != o.x ? x < o.x : y < o.y; }

    bool operator==(const Point &o) const { return fabs(x-o.x) < EPS && fabs(y-o.y) < EPS; }

    double cross(const Point &o) const { return x * o.y - y * o.x; }

    double dot(const Point &o) const { return x * o.x + y * o.y; }

    double atan() const { return atan2(y, x); }

    double norm() const { return sqrt(dot(*this)); }

    double distance(const Point &o) const { return (o - (*this)).norm(); }

    double area(const Point &a,const Point &b) {
        Point p = a - (*this), p2 = b - (*this);
        return p.cross(p2);
    }

    double area_abs(const Point &a,const Point &b) const {
        Point p = a - (*this), p2 = b - (*this);
        return fabs(p.cross(p2)) / 2.0;
    }  

    //線分abが自身に含まれているのかどうか判断する
    int between(const Point &a,const Point &b) {
        if(area(a,b) != 0) return 0;

        if(a.x != b.x)  return ((a.x <= x) && (x <= b.x) || (a.x >= x) && (x >= b.x));
        else return ((a.y <= y) && (y <= b.y) || (a.y >= y) && (y >= b.y));
    }

    double distance_seg(const Point& a,const Point& b) {
        if((b-a).dot(*this-a) < EPS) {
            return (*this-a).norm();
        }
        if((a-b).dot(*this-b) < EPS) {
            return (*this-b).norm();
        }
        return abs((b-a).cross(*this-a)) / (b-a).norm();
    }

    bool hitPolygon(const Point& a,const Point& b,const Point& c) {
        double t = (b-a).cross(*this-b);
        double t2 = (c-b).cross(*this-c);
        double t3 = (a-c).cross(*this-a);   

        if((t > 0 && t2 > 0 && t3 > 0) || ( t < 0 && t2 < 0 && t3 < 0)) {
            return true;
        }

        return false;
    }
};

struct Circle {
    Point p;
    double r;

    Circle() : p(Point(0,0)), r(0) {}

    Circle(Point o, double r) : p(o), r(r) {}

    Circle(double x,double y, double r) : p(Point(x,y)), r(r) {}

    bool isCircleIn(const Point& o) {
        Point res = o-p;
        return res.dot(res) < r*r + EPS;
    }

    // 1:外で接する，0:交差なし，-1:内で接する，2:交差，-2:内包
    int isIntersect(const Circle& c) {
        double d = (c.p - p).dot(c.p - p);
        double len = (c.r + r) * (c.r + r);

        if(equals(d,len)) return 1;
        if(d > len) return 0;

        double R = fabs(c.r - r) * fabs(c.r - r);
        if(equals(d,R)) return -1;
        if(d > R) return 2;
        return -2;
    }

    vector<Point> getCrossPoint(const Circle& c) {
        vector<Point> ret;
        int ch = isIntersect(c);

        if(ch == 0 || ch == -2) return ret;

        Point base = c.p - p;
        double len = base.dot(base);
        double t = (r*r - c.r*c.r + len) / (2.0 * len);

        if(ch == 2) {
            Point n(-base.y,base.x);
            n = n / (n.norm());
            double h = sqrt(r * r - t*t*len);

            ret.push_back(p + (base*t) + (n*h));
            ret.push_back(p + (base*t) - (n*h));
        } else {
            ret.push_back(p + (base*t));
        }

        return ret;
    }
};

int main() {
    int n,m;

    while(cin >> n && n) {
        vector<Circle> v;
        rep(i,n) {
            double x,y,r;
            cin >> x >> y >> r;

            v.push_back(Circle(x,y,r));
        }

        int m;
        cin >> m;

        rep(q,m) {
            Point t,o;
            cin >> t.x >> t.y >> o.x >> o.y;

            bool flag = true;

            rep(i,n) {
                if(v[i].isCircleIn(t) && v[i].isCircleIn(o)) {
                    continue;
                } else if(!v[i].isCircleIn(t) && !v[i].isCircleIn(o)) {
                    double d = v[i].p.distance_seg(t,o);
                    if(d < v[i].r + EPS) flag = false;
                } else {
                    flag = false;
                }
            }

            if(flag) cout << "Danger" << endl;
            else cout << "Safe" << endl;
        }
    }

    return 0;
}
Aug 28th, 2015
aoj, 幾何

ケーキを作った

実家に帰省し，教習所に通っている．仮免許を取ることが出来てワイワイである．気分もいいのでケーキでも作ろうと思い，ガトーショコラを作った(正確にはガトー・オ・ショコラらしい)．特にblogを更新するネタも無いので，これをblogにあげてしまおうという魂胆だ．

材料

  • チョコレート 140
  • バター 120g
  • 卵 6個
  • さとう 120g
  • 生クリーム
  • 小麦粉 40g
  • ココア 50g

方法

まず始めに小麦粉とココアを混ぜてふるう．

するとこのような感じになる．

次に，チョコとバターを湯煎していく．

こうなれば終了である．加減が難しい

次に卵を卵黄と，卵白に分ける．

最初は卵黄のほうをする．砂糖を3回に分けて入れていく．

混ぜる，ひたすら混ぜる．つらい．めっちゃ混ぜた後，マヨネーズのような感じになる．

次は卵白だ．いわゆるメレンゲを作る．これはハンドミキサーを使う．

同様に砂糖を3回に分けて入れていく．

いい感じになるまでやる．つらい．

いい感じになった．

先ほどの卵黄を混ぜたものに，湯煎したチョコを入れる．

続いて生クリームも入れる．

さらに振るった小麦粉とココアを再度振るいながら入れる．

混ぜていくと生地っぽくなる．

最後に，メレンゲを3回に分けて入れていく．泡を潰さないように混ぜていくのがポイントらしい．

生地が出来た．

型に入れていく．

オーブンで焼いて完成．

終わりに

ガトーショコラ，ただひたすら混ぜるだけでつらい．でも美味しいので満足．色々なケーキを作ってみたい．

Aug 13th, 2015
ケーキ, 料理