C++の練習を兼ねて, 競プロ典型 90 問 の 問題009 (Three Point Angle) を解いてみた.
■感想.
1. 問題009は, 何となく過去問の解説 (D – 三角形の分類) の方針が利用できるように見えたので, AC版に到達出来たと思う.
2. 尺取り法 の 復習ができたので 非常に良かったと思う.
3. 手強い問題が非常に多い気もするけど, 時間を見つけて, 引き続き, 取り組んでいきたいと思う.
詳細は, 本家のサイト(GitHub) 競プロ典型 90 問 の 問題009 を ご覧下さい.
■C++版プログラム(問題009／AC版).
|
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 |
// C++(GCC 9.2.1) #include <bits/stdc++.h> using namespace std; #define repex(i, a, b, c) for(int i = a; i < b; i += c) #define repx(i, a, b) repex(i, a, b, 1) #define rep(i, n) repx(i, 0, n) #define repr(i, a, b) for(int i = a; i >= b; i--) #define pb push_back #define all(x) x.begin(), x.end() const double PI = acos(-1); int x[2020], y[2020]; struct rotation{ int x, y; double a; bool operator < (const rotation& rhs) const{ return a < rhs.a; } }; int main(){ // 1. 入力情報. int N; scanf("%d", &N); rep(i, N){ int a, b; scanf("%d %d", &a, &b); x[i] = a; y[i] = b; } // 2. ベクトルの角度を計算. double ans = 0.0; rep(i, N){ // 2-1. 点P[j] を 固定. vector<int> bx, by; rep(j, N){ if(j == i) continue; bx.pb(x[j] - x[i]); by.pb(y[j] - y[i]); } // 2-2. 角度(1周分) を 保存. vector<rotation> angle; rep(j, bx.size()){ // atan2 は, [-PI, PI] で 返却されることに注意. double a = atan2(by[j], bx[j]); if(a < 0.0) a += PI * 2.0; rotation r; r.x = bx[j]; r.y = by[j]; r.a = a; angle.pb(r); } // 2-3. 角度 を sort. sort(all(angle)); // 2-4. 角度(2周分) に 水増し. int n = angle.size(); rep(j, n){ rotation r; r.x = angle[j].x; r.y = angle[j].y; r.a = angle[j].a + PI * 2.0; angle.pb(r); } // for(auto &p : angle) printf("%d %d %lf\n", p.x, p.y, p.a); // 2-5. 角度の最大値は？ int l = 0, r = 1; double cur = 0.0; while(l < n){ double diff = 0.0; while(r < l + n){ // 角度を取得. diff = angle[r].a - angle[l].a; // 180度を超えた場合は, 一つ前の r を使って, 探索終了. if(diff > PI){ r--; diff = angle[r].a - angle[l].a; break; } // 180度の場合は, 探索終了. if(diff == PI) break; // r を increment. r++; } // l を increment. l++; // 最大値更新. cur = max(cur, diff); } // 2-6. 最大値更新. ans = max(ans, cur); } // 3. 出力. printf("%.12lf\n", ans / PI * 180.0); return 0; } |
|
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 |
[入力例] 3 0 0 0 10 10 10 [出力例] 90 ※AtCoderテストケースより ※但し, 上記のプログラムでは, 以下の内容が出力される. 90.000000000000 [入力例] 5 8 6 9 1 2 0 1 0 0 1 [出力例] 171.869897645844 ※AtCoderテストケースより [入力例] 10 0 0 1 7 2 6 2 8 3 5 5 5 6 7 7 1 7 9 8 8 [出力例] 180 ※AtCoderテストケースより ※但し, 上記のプログラムでは, 以下の内容が出力される. 180.000000000000 [入力例] 40 298750376 229032640 602876667 944779015 909539868 533609371 231368330 445484152 408704870 850216874 349286798 30417810 807260002 554049450 40706045 380488344 749325840 801881841 459457853 66691229 5235900 8100458 46697277 997429858 827651689 790051948 981897272 271364774 536232393 997361572 449659237 602191750 294800444 346669663 792837293 277667068 997282249 468293808 444906878 702693341 894286137 845317003 27053625 926547765 739689211 447395911 902031510 326127348 582956343 842918193 235655766 844300842 438389323 406413067 862896425 464876303 68833418 76340212 911399808 745744264 551223563 854507876 196296968 52144186 431165823 275217640 424495332 847375861 337078801 83054466 648322745 694789156 301518763 319851750 432518459 772897937 630628124 581390864 313132255 350770227 [出力例] 179.9834340684232 ※AtCoderテストケースより ※但し, 上記のプログラムでは, 以下の内容が出力される. 179.983434068423 [入力例] 10 24 9 77 72 0 4 13 73 51 105 100 104 72 23 0 26 62 16 120 49 [出力例] 178.669186419098 [入力例] 20 1635 10426 7389 8009 10003 10431 7740 1110 5013 6171 4086 8267 209 1918 304 10739 3845 270 2296 260 11754 4025 3574 11342 11595 3431 4631 2738 4790 5436 1230 68 9420 9848 3010 9007 5451 6745 9511 10460 [出力例] 179.896865785287 [入力例] 30 7158389 10413815 6070867 151525 4958107 5169148 4360871 9883042 8892018 2127037 3220360 7466394 6867253 7301852 11921852 4646440 5647521 11730630 4478503 2578017 3427913 11428302 7441405 2060342 4200045 555865 3115916 12322024 3952701 490350 4650035 632956 9619727 2197121 10424915 6817438 7780200 8796458 5659878 10310152 8771320 7675027 11080686 12322081 315038 4030589 736617 8845875 848867 10840290 7079095 7947504 3373068 6395890 5469078 5321751 8258439 9651831 8611025 4864387 [出力例] 179.976838213525 |
■参照サイト
009 – Three Point Angle
AtCoder Beginner Contest 033 (D – 三角形の分類)