Subtask 1 (14 คะแนน) $x_1[i]=x_2[i]$ และ $y_1[i]=y_2[i]$

ในปัญหาย่อยนี้จะมีเพียงจุดเท่านั้น ดังนั้นหากเราสามารถตรวจสอบได้ว่าจุดใดบดบังกันก็สามารถลบจุดที่โดนบดบังออกได้เลย จุดหนึ่งจุดจะบดบังหรือโดนบดบังเป็นเส้นตรงที่ลากจาก $(0,0)$ และ $(x[i],y[i])$ ดังนั้นหากมีเส้นตรงสองเส้นที่่ความชันเท่ากันแล้ว จะมีหนึ่งในสองจุดที่ต้องนำออก ในการเก็บความชันของจุดก่อน ๆ สามารถใช้ data structure อย่าง std::set หรือ std::unordered_set เพื่อเพิ่มและตรวจ สอบความชันที่เคยใส่แล้วได้โดยการนำ $\gcd(x, y)$ ไปหารทั้ง $y$ และ $x$ ให้อยู่ในรูปของเศษส่วนอย่างต่ำก่อนใส่ใน set นั่นเอง

Time Complexity: $\mathcal{O}(N\log N)$

Subtask 2 (25 คะแนน) $y_1[i]=y_2[i]=1$

เนื่องจาก $y_1[i]=y2[i]=1$ เราสามารถพิจารณาช่วงที่โดนบดบังในแกน $y=1$ ได้ สังเกตว่าเส้นส้มหนึ่งเส้นจะตัดกับเส้นตรง $y=1$ ที่จุด $x_1[i]$ และ $x_2[i]$ ซึ่งมองเป็นช่วงที่จะโดนบดบังได้ ดังนั้นหากเราหาได้ว่าต้องเลือกช่วงให้มีเส้นส้มได้มากที่สุดอย่างไร ก็จะสามารถตอบได้ว่าต้องถอนเส้นส้มออกอย่างน้อยที่สุดกี่เส้น ซึ่งปัญหานี้ก็สามารถแก้ไขได้ด้วยอัลกอริทึมคลาสสิกอย่าง Interval Scheduling¹ โดย Interval Scheduling เป็น greedy algorithm ที่จะทำการ sort ช่วงตามจุดจบและเลือกเส้นที่เลือกได้ทันที จากนั้นเมื่อพิจารณาช่วงถัด ๆ ไปก็จะพิจารณาว่าจุดเริ่มต้นซ้อนทับจุดสิ้นสุดของช่วงที่เคยเลือกไว้หรือไม่

Time Complexity: $\mathcal{O}(N\log N)$

Subtask 3 (26 คะแนน) $N\leq 20$

ข้อสังเกต #1: หากเลือกเส้นตรงหนึ่งเส้นจะมีช่วงที่ไม่สามารถเลือกได้เกิดขึ้น ซึ่งช่วงนั้นจะอยู่ระหว่างเส้นตรงที่ลากจาก $(0,0)$ ไปยัง $(x_1[i],y_1[i])$ และ $(x_2[i],y2[i])$ โดยเราสามารถมองเป็นช่วงของความชันได้ ในที่นี้เรียกค่าความชันที่น้อยกว่าว่า "ความชันเริ่มต้น" และ เรียกค่าที่มากกว่าว่า "ความชันสิ้นสุด"

ปัญหาย่อยนี้สามารถแก้ได้ด้วยการทดลองทำตามเงื่อนไขโจทย์โดยตรงด้วยการเลือกสับเซตของเส้นส้มที่ต้องการเอาออกและตรวจสอบว่าเส้นส้มที่เหลืออยู่แต่ละเส้นตัดกันหรือไม่ (ใช้แนวคิดจากข้อสังเกต 1) เนื่องจากเรามีสับเซตที่เป็นไปได้ทั้งหมด $2^N$ สับเซต และการตรวจสอบว่าเส้นส้มเส้นหนึ่งตัดกับเส้นใด ๆ หรือไม่สามารถทำได้ใน $\mathcal{O}(N^2)$ ทำให้เราสามารถแก้ปัญหานี้ได้ใน $\mathcal{O}(N^22^N)$ ซึ่งเพียงพอสำหรับค่า $N\leq 20$

หมายเหตุ : ระวังช่วงที่มีความชันเริ่มต้นเท่ากับความชันสิ้นสุดของเส้นก่อนหน้า ไม่สามารถเลือกสองช่วงนั้น ๆ ได้

Time Complexity: $\mathcal{O}(N^22^N)$

Subtask 4 (18 คะแนน) $N\leq 2\,000$

ในปัญหาย่อยนี้สามารถใช้ Dynamic Programming ในการแก้ได้ นิยามความชันเริ่มต้นและความชันสิ้นสุดเป็นค่าน้อยกว่าและค่ามากกว่า ระหว่าง $y_1[i]/x_1[i]$ และ $y_2[i]/x_2[i]$ ตามลำดับ หากเราพิจารณาเส้นส้มจากค่าความชันเริ่มต้นที่เรียงจากน้อยไปมาก ในเส้นส้มลำดับที่ $i$ จะได้สมการของอาเรย์ $dp$ ว่า

$dp[k]=\max(dp[k],dp[i]+1) \small\text{ สำหรับทุก ๆ เส้นส้ม } k \small\text{ ที่ความชันเริ่มต้น } > \small\text{ ความชันสิ้นสุดของ } i$

ทำให้เราสามารถคำนวณ $dp$ ได้ใน $\mathcal{O}(N)$ สำหรับแต่ละเส้นส้ม และส่งผลให้แก้ปัญหาทั้งหมดได้ใน $\mathcal{O}(N^2)$

Time Complexity: $\mathcal{O}(N^2)$

Official Solution

หากเราสังเกตโครงสร้างของปัญหานี้ด้วยการใช้แนวคิดจากปัญหาย่อยที่ 2 และ 3 เราจะสามารถตรวจสอบได้ว่าเราเลือกเส้นส้มได้ทั้งหมดกี่เส้นด้วยอัลกอริทึมอย่าง Interval Scheduling¹ บนความชันความชันเริ่มต้นและความชันสิ้นสุดได้ และได้ว่าจำนวนเส้นส้มที่น้อยที่สุดที่ต้องถอนจะเท่ากับ $N$ ลบด้วยจำนวนเส้นส้มที่มากที่สุดที่สามารถเลือกได้ ในปัญหานี้ได้ถูกออกแบบให้สามารถใช้ตัวแปรประเภท double เก็บข้อมูลได้ (การใช้ float จะทำให้คำตอบที่ผิด) อย่างไรก็ตามหากมีการเปรียบเทียบที่มีความแม่นยำมากกว่านี้ควรเก็บตัวแปรเป็น long long ของจำนวนเต็มและใช้วิธีการคูณไขว้เพื่อเทียบความชันในรูปเศษส่วนแทน โดยที่

$\frac{A}{B}\leq\frac{C}{D}\Longleftrightarrow AD\leq CB$

เมื่อเรา assume ว่า $B,D>0$

Time Complexity: $\mathcal{O}(N\log N)$

¹ข้อมูลเพิ่มเติมของ interval scheduling สามารถศึกษาได้ที่ https://en.wikipedia.org/wiki/Interval_scheduling

Solution Code

#pragma GCC optimize("O3")
#include<bits/stdc++.h>
#define pii pair<int, int>
#define pII pair<pii, pii>
#define pll pair<long long, long long>
#define ll long long
#define ld long double
#define st first
#define nd second
#define pb push_back
#define INF INT_MAX
#define sz(x) x.size()
using namespace std;

const int N = 1e5 + 10;

pair<pll, pll> line[N];

bool cmp(pair<pll, pll> a, pair<pll, pll> b) {
    pll cur_a = a.nd;
    pll cur_b = b.nd;
    return cur_b.st*cur_a.nd < cur_a.st*cur_b.nd;
}

void solve() {
    int n; cin >> n;
    for (int i = 1; i <= n; ++i) {
        ll x, y, z, w; cin >> x >> y >> z >> w;
        if (y*z > w*x) swap(x, z), swap(y, w);
        line[i] = {{x, y}, {z, w}};
    }
    sort(line+1, line+n+1, cmp);
    int cnt = n;
    pll cur = {1, -1};
    for (int i = 1; i <= n; ++i) {
        auto [x, y] = line[i].st;
        if (cur.nd*x >= cur.st*y) continue;
        cnt--;
        cur = line[i].nd;
    }
    cout << cnt << '\n';
}

int main() {
    ios_base::sync_with_stdio(0); cin.tie(NULL);
    int t = 1;
//    cin >> t;
    while (t--) {
        solve();
    }
}