2026-11-17
sort_by_angle.cpp
struct P {
long long x, y;
};
void sort_by_angle(std::vector<P>& ps) {
}
原点と異なる整数座標の点を並べた ps を、x 軸の正の向きから反時計回りに測った角度の小さい順に並べ替える sort_by_angle を書いてください。角度は 0 度以上 360 度未満で測り、x 軸の正の向きにある点の角度は 0 度です。原点から見て同じ向きにある点が2つ以上含まれることはありません。座標の絶対値は 109 以下で、向きのわずかな違いも区別できるように、浮動小数点数は使わず整数の計算だけで比べてください。ps の要素が1つ以下なら何もしません。例では、呼び出す前と後の ps の中身を {x, y} の並びで書きます。
入力例 1
{{0, -1}, {-1, 0}, {0, 1}, {1, 0}}
出力例 1
{{1, 0}, {0, 1}, {-1, 0}, {0, -1}}
入力例 2
{{-3, -1}, {2, 5}, {1, -1}, {-4, 2}, {3, 0}}
出力例 2
{{3, 0}, {2, 5}, {-4, 2}, {-3, -1}, {1, -1}}
入力例 3
{{1000000000, 999999999}, {999999999, 999999998}}
出力例 3
{{999999999, 999999998}, {1000000000, 999999999}}
Reference
Reference
struct P {
long long x, y;
};
bool upper(P p) {
return p.y > 0 || (p.y == 0 && p.x > 0);
}
void sort_by_angle(std::vector<P>& ps) {
std::ranges::sort(ps, [](P a, P b) {
if (upper(a) != upper(b))
return upper(a);
return a.x * b.y - a.y * b.x > 0;
});
}
原点から見た向きは、外積1 a.x * b.y - a.y * b.x の符号で比べられます。正なら b は a から反時計回りに 180 度未満だけ回った側に、負なら時計回りの側にあります。ところが、この符号をそのまま「a が先」の判定にすると、一周にわたっては並び順になりません。(1, 0)、(-1, 1)、(-1, -1) の3点では、どの隣り合う2点の外積も正になり、1つ目は2つ目より先、2つ目は3つ目より先、3つ目は1つ目より先、と順序が循環します。std::ranges::sort は、比較関数が「先」を矛盾なく決めること(狭義の弱順序2)を要求するので、循環する比較を渡すと結果は保証されません。掲載したのは参考実装で、唯一の正解ではありません。
循環が起きるのは、外積が「180 度未満の回転でどちら側か」しか答えないのに、点が一周にわたって散らばっているからです。そこで円を、角度が 0 度以上 180 度未満の半分と、180 度以上 360 度未満の半分に切ります。upper は前の半分にある点で真になり、y 座標が正の点のほかに、x 軸の正の向きの点(角度 0 度)も含めます。x 軸の負の向きの点(180 度)は後ろの半分です。半分が違う2点は前の半分の点を先にし、同じ半分にある2点は向きの差が 180 度未満なので、外積の符号で前後が矛盾なく決まります。入力例 1 では (1, 0) と (0, 1) が前の半分、(-1, 0) と (0, -1) が後ろの半分に分かれます。
座標の絶対値が 109 以下なら、外積の各項は 1018 以下、差は 2 × 1018 以下で、long long の最大値(約 9.2 × 1018)に収まります。入力例 3 の2点は、外積が 109 × 999999998 − 999999999 × 999999999 = −1 で、2つ目が1つ目より時計回りの側にあるので先に来ます。2点の角度の差は 10−18 ラジアン程度で、double で角度を計算すると同じ値になり、区別できません。
- ここでの外積(cross product)は、平面のベクトル (a, b) と (c, d) に対する a × d − b × c のことです。2つのベクトルが作る平行四辺形の面積に、2つ目が1つ目の反時計回りの側にあれば正、時計回りの側にあれば負の符号を付けた値になります。
- 狭義の弱順序(strict weak ordering)は、比較関数に求められる条件です。a が b より先なら b は a より先ではなく、a が b より先で b が c より先なら a は c より先、などを満たす必要があります。