Namaran

Code daily. Without assist.

2026-09-02

turn.c

#include <stdio.h>

struct pixel { unsigned x, y; };

static int turn(struct pixel a, struct pixel b, struct pixel c) {
    long long ux = b.x - a.x, uy = b.y - a.y;
    long long vx = c.x - a.x, vy = c.y - a.y;
    long long cross = ux * vy - uy * vx;
    return (cross > 0) - (cross < 0);
}

int main(void) {
    struct pixel a = {10, 10}, b = {20, 10}, c = {15, 5};
    printf("%d\n", turn(a, b, c));
}

turn は、x 軸を右、y 軸を上に取った座標で、a から b へ進んだときに c が左にあれば 1、右にあれば -1、一直線上なら 0 を返すつもりの関数です。判定には、ベクトル a→b と a→c の外積(cross product)ux × vy − uy × vx の符号を使っています。main の a = (10, 10)、b = (20, 10)、c = (15, 5) では c は右にあるので、本来は -1 と表示されるはずですが、いまは 1 と表示されます。

Answer

Wrong

long long ux = b.x - a.x, uy = b.y - a.y;
long long vx = c.x - a.x, vy = c.y - a.y;

代入先は long long ですが、c.y - a.y のような引き算は、代入より先に unsigned どうしで計算されます。符号なし整数の引き算は負の値にならず、unsigned が32ビットなら結果は2の32乗で割った余りになります1。5 − 10 は −5 ではなく 4294967291 になり、その値のまま vy に入ります。

すると外積は 10 × 4294967291 − 0 × 5 という大きな正の数になり、turn は c が左にあると判断して 1 を返します。差が負になるのは b や c の座標が a より小さいときで、そのような点では外積の符号が意図と食い違うことがあります。

Right

long long ux = (long long)b.x - a.x, uy = (long long)b.y - a.y;
long long vx = (long long)c.x - a.x, vy = (long long)c.y - a.y;

引かれる側を先に long long へ変換すると、通常の算術変換で unsigned の側も long long に変換されてから引き算が行われます。long long は32ビットの unsigned の値をすべて表せるので、5 − 10 は −5 のまま残り、外積は 10 × (−5) − 0 × 5 = −50 で、turn は -1 を返します。

  1. 符号付き整数が範囲を超えるのは未定義動作ですが、符号なし整数の演算は最大値に1を足した数で割った余りになると規格が定めています。誤りではなく定義された動作なので、未定義動作を検出するサニタイザもこの引き算では止まりません。