2D μ’νκ³μμ μΈνμ λ¬Έμ λ₯Ό μκ°ν΄λ³΄μ. μ μ , , ..., μ μμμ μμλ‘ μ λΆ μννκ³ λ€μ μΆλ°ν μ μ μΌλ‘ λμμ¨λ€κ³ ν λ, ν΄λΉ κ²½λ‘μ ν΄λ¦¬μ€ν±μ μΈ μ΅λ¨κ±°λ¦¬λ μ΄λ»κ² λ κ²μΈκ°?
ν΄λ¦¬μ€ν±μ μΌλ‘λ μ΄λ κ² μκ°ν μ μλ€. λͺ¨λ μ’νμ νκ· μ λ΄μ κ°μμ μ κ° μλ€κ³ ν΄λ³΄μ. κ·Έλ¬λ©΄ μ£Όλ³μ μ λ€μ μ΄ κ°μμ μ μ λλ¬μΌ μμ ννλ₯Ό κ°μ§κ² λ κ²μΌλ‘ μκ°ν μ μλ€. κ·Έλ¬λ©΄ μ΄ μ’νλ€μ μμ κ·Έλ¦¬λ― μννλ λ°©λ²μ΄ μ΅λ¨κ±°λ¦¬λ μλλλΌλ μ΄λ μ λ ν΄λ¦¬μ€ν±μ μ λ΅μ μ ν¨νλ€κ³ μΆμΈ‘ν΄λ³Ό μ μλ€.
μ΄λ₯Ό ꡬ체μ μΌλ‘ ꡬννκΈ° μν΄μλ κ°λ μ λ ¬μ΄ νμνλ€. νκ· μ λΆν°μ κ° μ μ , μ’νμ 거리 μ°¨μ΄λ₯Ό , λΌ νμ. κ·Έλ¬λ©΄, μμμ μ κ³Ό μΆμ΄ μ΄λ£¨λ κ°λλ₯Ό λΌ ν λ, ν¨μμ μ μμ μν΄, λ μλμ κ°μ΄ ꡬν μ μλ€.
λν μ΄ ν¨μκ°μ λ²μλ ν¨μ μ μμ λ°λΌ μλ λ²μλ‘ bound λλ€.
μ΄ μ±μ§μ νμ©νλ©΄, xμΆμΌλ‘λΆν° μκ³ λ°λλ°©ν₯μΌλ‘ λμκ°λ μμλ‘ μ’νλ₯Ό μ λ ¬λκ² νλ €λ©΄, μλμ²λΌ λΆκΈ°μν¬ μ μλ€.
μ΄λ ν¨μμ κ°νκ³Ό, κ·Έ μ΅λ / μ΅μκ°μ μκ°ν΄λ³΄λ©΄ λͺ λ°±νλ€. μΆμ μλ μ’νλ κ·Έ μ΄λ€ μͺ½μ μ νν΄λ κ°μ΄ κ°λ€.
μ΄λ‘μ μ°λ¦¬λ, κ·Έ μ΄λ€ math
libraryλ₯Ό μ°μ§ μκ³ λ, κ°λλ‘ μ’νλ€μ μ λ ¬νλ€. μμ λμμ½λλ μλμ κ°μ΄ κ°λ¨ν μμ±ν΄λ³΄μλ€.
struct Point {int x, y;};double getKey(Point& a) {int ret = 0;int x = a.x, y = a.y;if (x == 0 && y == 0) return 0;double sin2 = 1.0 * y * y / (x * x + y * y);if (x >= 0 && y > 0) {return sin2;}else if (x < 0 && y >= 0) {return 2 - sin2;}else if (x <= 0 && y < 0) {return 2 + sin2;}else {return 4 - sin2;}return ret;}void test() {vector<Point> v;v.push_back({ 3, 1 });v.push_back({ 1, 2 });v.push_back({ 0, 4 });v.push_back({ -1, 3 });v.push_back({ -5, 2 });v.push_back({ -6, 0 });v.push_back({ -1, -1 });v.push_back({ 0, -3 });v.push_back({ 2, -3 });v.push_back({ 5, -1 });v.push_back({ 1, 0 });random_shuffle(v.begin(), v.end()); // λλ€μΌλ‘ μμ΄μ μ μμλ‘ λ³΅κ΅¬λλμ§ λ³΄μsort(v.begin(), v.end(), [&](Point& a, Point& b) {return getKey(a) < getKey(b);});for (auto& p : v) {printf("%d, %d\n", p.x, p.y);}}
vector
μ λ£κ³ μλ μμλλ‘ μΆλ ₯μ΄ λμ€λ©΄ μ μμ μΌλ‘ μ λ ¬λ κ²μ΄λ€. λ§μ½ κ°λμ μ€μΉΌλΌμ ν¬κΈ°κ° μ μ ν λ°°λΆλλ©΄μ μ λ ¬λκΈ°λ₯Ό μνλ€λ©΄, κ·Έ λν keyκ°μ μ‘°μ νλ©΄ κ°λ₯νλ€.