Unique Fractions in C++: ลดรูปเศษส่วน ลบซ้ำ เรียงลำดับ

กำหนดให้มีรายการเศษส่วน โดยแต่ละเศษส่วนมีรูปแบบ [numerator, denominator] เราต้องสร้างรายการใหม่ที่:

• เศษส่วนอยู่ในรูปลดรูปแล้ว (เช่น 20/14 → 10/7)
• ลบเศษส่วนซ้ำออก (หลังลดรูปแล้ว)
• เรียงลำดับจากน้อยไปมากตามค่าจริงของเศษส่วน
• เครื่องหมายลบอยู่ที่ตัวเศษเสมอ

ตัวอย่าง: {{16,8},{4,2},{7,3},{14,6},{20,4},{-6,12}} → [[-1,2],[2,1],[7,3],[5,1]]

วิธีแก้ปัญหา

1. ลดรูปเศษส่วนแต่ละตัวด้วย GCD
2. จัดเก็บใน vector แล้วเรียงตามค่า numerator/denominator
3. ลบเศษส่วนซ้ำที่อยู่ติดกันหลังเรียงแล้ว

ตัวอย่างโค้ด C++

#include <bits/stdc++.h>
using namespace std;

class Solution {
public:
    static bool cmp(vector<int>& a, vector<int>& b) {
        return (double)a[0]/a[1] < (double)b[0]/b[1];
    }
    vector<vector<int>> solve(vector<vector<int>>& v) {
        set<vector<int>> s;
        vector<vector<int>> r;
        for(auto& frac : v) {
            int g = __gcd(abs(frac[0]), abs(frac[1]));
            frac[0] /= g; frac[1] /= g;
            r.push_back({frac[0], frac[1]});
        }
        sort(r.begin(), r.end(), cmp);
        vector<vector<int>> ret;
        for(auto& f : r) {
            if(!ret.empty() && ret.back() == f) continue;
            ret.push_back(f);
        }
        return ret;
    }
};

int main() {
    vector<vector<int>> v = {{16,8},{4,2},{7,3},{14,6},{20,4},{-6,12}};
    Solution ob;
    // print result...
}

Input

{{16,8},{4,2},{7,3},{14,6},{20,4},{-6,12}}

Output

[[-1,2],[2,1],[7,3],[5,1]]