Namaran

Code daily. Without assist.

2026-09-02

left_turns.c

#include <stddef.h>

struct point { int x, y; };

size_t count_left_turns(const struct point *p, size_t n) {
}

折れ線の頂点 p[0], p[1], …, p[n - 1] を順にたどるとき、左に曲がる頂点の数を返す count_left_turns を書いてください。p[i - 1] から p[i] へのベクトルを (ux, uy)、p[i] から p[i + 1] へのベクトルを (vx, vy) とします。ux × vy − uy × vx をこの2つのベクトルの外積(cross product)といい、外積が正のとき p[i] で左に曲がったといいます。外積が0や負の頂点は数えません。n が2以下なら0を返します。座標の絶対値は1000以下です。

入力例 1

count_left_turns((struct point[]){{0, 0}, {2, 0}, {2, 2}, {0, 2}}, 4)

出力例 1

2

入力例 2

count_left_turns((struct point[]){{0, 0}, {1, 1}, {2, 0}, {3, 1}}, 4)

出力例 2

1

入力例 3

count_left_turns((struct point[]){{0, 0}, {5, 5}}, 2)

出力例 3

0
Reference
size_t count_left_turns(const struct point *p, size_t n) {
    size_t count = 0;
    for (size_t i = 1; i + 1 < n; i++) {
        int ux = p[i].x - p[i - 1].x, uy = p[i].y - p[i - 1].y;
        int vx = p[i + 1].x - p[i].x, vy = p[i + 1].y - p[i].y;
        if (ux * vy - uy * vx > 0)
            count++;
    }
    return count;
}

両端を除く頂点 p[i] ごとに、手前の辺と次の辺のベクトルを作り、外積の符号を見ます。入力例2では、p[1] で (1, 1) から (1, −1) へ向きが変わり、外積は 1 × (−1) − 1 × 1 = −2 なので右に曲がります。p[2] では (1, −1) から (1, 1) へ変わり、外積は 1 × 1 − (−1) × 1 = 2 なので左です。左に曲がるのは1か所なので、1を返します1。

ループの条件を i < n - 1 ではなく i + 1 < n と書いているのは、n が size_t だからです。符号なしの引き算は負にならず、n が0のとき n - 1 は size_t の最大値に回り込むので、ループが回って配列の外を読みます。i + 1 < n なら引き算がないので、n が0でも1でもループは1回も回りません。

掲載したのは参考実装で、唯一の正解ではありません。3点を受け取って外積を返す関数に分けても同じです。

  1. 外積の絶対値は、2つのベクトルが作る平行四辺形の面積です。2辺を (x1, y1) と (x2, y2) とする三角形の面積は、高校で習う公式で S = 1/2 |x1y2 − x2y1| と表され、絶対値の中身が、ちょうどこの外積にあたります。符号は、2本目のベクトルが1本目から見て反時計回りの側にあれば正、時計回りの側にあれば負になります。