C++の練習を兼ねて, AtCoder Beginner Contest 248 の 問題E (K-colinear Line) を解いてみた.
■感想.
1. 問題Eは, 方針が見えなかったので, 解説を参考に, AC版に到達できたと思う.
2. 個人的には, 直線を固定して数え上げていくロジックが, 非常に面白く感じた.
3. 引き続き, 時間を見つけて, 過去問の学習を進めていきたいと思う.
本家のサイト AtCoder Beginner Contest 248 解説 の 各リンク を ご覧下さい.
■C++版プログラム(問題E/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 |
// 解き直し. // https://atcoder.jp/contests/abc248/editorial/3792 // C++(GCC 9.2.1) #include <bits/stdc++.h> using namespace std; using LL = long long; using P = pair<LL, LL>; using vp = vector<P>; using T3 = tuple<LL, LL, LL>; #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 a first #define b second #define pb push_back int main(){ // 1. 入力情報. int N, K; scanf("%d %d", &N, &K); vp v; rep(i, N){ LL x, y; scanf("%lld %lld", &x, &y); v.pb({x, y}); } // 2. K = 1. if(K == 1){ puts("Infinity"); return 0; } // 3. K != 1. map<T3, int> m; rep(i, N){ repx(j, i + 1, N){ // 二点 A, B. LL ax = v[i].a, ay = v[i].b; LL bx = v[j].a, by = v[j].b; // 傾き(ベクトル AB). LL vx = bx - ax, vy = by - ay; LL g = __gcd(abs(vx), abs(vy)); vx /= g; vy /= g; if(vx == 0) vy = 1; if(vy == 0) vx = 1; if(vx < 0){ vx *= -1; vy *= -1; } // 切片(但し, vx倍したものを取得). LL c = ay * vx - ax * vy; // 二点通る(初回のみ, 二回目以降は, 調査済みとして, Skip). if(!m.count({vx, vy, c})) m[{vx, vy, c}] = 2; else continue; // 全探索. rep(k, N){ // Skip. if(i == k || j == k) continue; // 点 P. LL px = v[k].a, py = v[k].b; // 傾き(ベクトル AP). LL wx = px - ax, wy = py - ay; // 判定. if(vx * wy == vy * wx) ++m[{vx, vy, c}]; } } } // 4. 集計. int ans = 0; for(auto &p : m) if(p.b >= K) ++ans; // 5. 出力. printf("%d\n", ans); 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 |
[入力例] 5 2 0 0 1 0 0 1 -1 0 0 -1 [出力例] 6 ※AtCoderテストケースより [入力例] 1 1 0 0 [出力例] Infinity ※AtCoderテストケースより [入力例] 3 2 1 2 2 0 2 1 [出力例] 3 [入力例] 10 3 30 -22 16 -19 -18 5 6 -12 -36 20 55 -29 -4 -5 77 41 60 -44 90 -66 [出力例] 2 [入力例] 30 3 6 12 -59 11 68 21 -29 60 16 22 63 16 24 93 43 40 36 42 42 52 -88 -53 73 26 -55 59 -8 22 86 35 -10 21 -66 51 13 -87 0 26 78 -36 -53 -57 10 31 -5 18 -28 49 -86 -79 -83 -77 10 47 -76 62 67 17 -26 -99 [出力例] 6 |
■参照サイト
ユニークビジョンプログラミングコンテスト2022(AtCoder Beginner Contest 248)