sweep line 扫描线略知略会

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

int n,cur,ans;
map<int, int> cnt;

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    cin >> n;
    for (int a, b, i = 1; i <= n; i++) {
        cin >> a >> b;
        cnt[a - 1]++;
        cnt[b]--;
    }

    for (auto pi:cnt) {
        ans = max(ans, cur);
        cur += pi.second;
    }
    cout << ans << endl;

    return 0;
}

#include <bits/stdc++.h>
 
#define  get0(x)  get<0>(x)
#define  get1(x)  get<1>(x)
#define  _debug(x) cerr<<#x<<" = "<<x<<endl
using namespace std;
typedef long long ll;
const int MAXN = 1e6 + 59;
const ll MOD = 1e9 + 7;
 
ll n, ans;
vector<tuple<int, int> > pos;
 
 
int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
 
 
    cin >> n;
 
    pos.emplace_back(0, 0);
    for (ll l, r, i = 1; i <= n; i++) {
        cin >> l >> r;
        pos.emplace_back(l + l, 1);
        pos.emplace_back(l + r, -2);
        pos.emplace_back(r + r, 1);
    }
    sort(pos.begin(), pos.end());
 
    ll cur = 0;
    ll del = 0;
    ll las = 0;
 
    for (auto &p:pos) {
        cur += (get0(p) - las) * del;
        del += get1(p);
        las = get0(p);
        ans = max(ans, cur);
    }
    cout << ans << endl;
    return 0;
}

#include <bits/stdc++.h>

#define  get0(x)  get<0>(x)
#define  get1(x)  get<1>(x)
#define  get2(x)  get<2>(x)
#define  _debug(x) cerr<<#x<<" = "<<x<<endl
using namespace std;
typedef long long  ll;
const int MAXN = 1e6 + 59;
const ll MOD = 1e9 + 7;
const ll INF = 1001;


typedef struct frac {
    ll a, b;

    frac() : a(0), b(1) {}

    frac(ll _a) : a(_a), b(1) {}

    frac(ll _a, ll _b) : a(_a), b(_b) {
        if (a == 0) {
            this->b = 1;
        }
        if (b < 0) {
            this->a = -_a;
            this->b = -_b;
        }
        ll g = __gcd(abs(a), abs(b));
        this->a /= g;
        this->b /= g;
    }

    frac operator+(const frac &rht) const {
        return frac(a * rht.b + b * rht.a, b * rht.b);
    }

    frac operator-(const frac &rht) const {
        return frac(a * rht.b - b * rht.a, b * rht.b);
    }

    frac operator*(const frac &rht) const {
        return frac(a * rht.a, b * rht.b);
    }

    frac operator/(const frac &rht) const {
        return frac(a * rht.b, b * rht.a);
    }

    bool operator<(const frac &rht) const {
        return a * rht.b < b * rht.a;
    }

    bool operator<=(const frac &rht) const {
        return a * rht.b <= b * rht.a;
    }

    bool operator>(const frac &rht) const {
        return a * rht.b > b * rht.a;
    }

    bool operator>=(const frac &rht) const {
        return a * rht.b >= b * rht.a;
    }

    bool operator==(const frac &rht) const {
        return a * rht.b == b * rht.a;
    }

    friend ostream &operator<<(ostream &out, frac &T);

    void operator()(ll _a, ll _b) {
        *this = frac(_a, _b);
    }
} fc;

ostream &operator<<(ostream &out, fc &T) {
    out << T.a << "/" << T.b;
    return out;
}

// y1<y2
fc calc1(fc x1, fc y1, fc x2, fc y2, fc c) {
    fc dx = x2 - x1;
    fc dy = y2 - y1;
    fc dc = c - y1;
    return x1 + dc * dx / dy;
}

// y1>y2
fc calc2(fc x1, fc y1, fc x2, fc y2, fc c) {
    fc dx = x2 - x1;
    fc dy = y1 - y2;
    fc dc = c - y2;
    return x2 - dc * dx / dy;
}

ll n, kase, c;
vector<tuple<fc, ll, ll> > pos;
vector<fc> ans;


int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    cin >> kase;
    while (kase--) {

        ans.clear();
        pos.clear();
        cin >> n >> c;

        fc prek(0);
        fc preb(0);
        fc lasx(-INF);
        fc lasy;
        fc v(c);

        //pos.emplace_back(-INF, 0, 0);
        for (ll _a, _b, i = 1; i <= n; i++) {
            cin >> _a >> _b;
            prek = prek + fc(-_a);
            preb = preb + fc(-_b);
            pos.emplace_back(frac(-_b, _a), 2 * _a, 2 * _b);// +inf ,+k
        }

        pos.emplace_back(INF, 0, 0);
        lasy = prek * lasx + preb;

        sort(pos.begin(), pos.end());

        bool infi = false;
        for (auto &p:pos) {

            fc x, y;
            ll k, b;
            tie(x, k, b) = p;
            y = (prek + k) * x + (preb + b);

            if (lasy == v && y == v) {
                ans.clear();
                infi = true;
                break;
            }

            if (lasy <= v && y > v) {
                ans.push_back(calc1(lasx, lasy, x, y, v));
            } else if (lasy >= v && y < v) {
                ans.push_back(calc2(lasx, lasy, x, y, v));
            }

            lasy = y;
            lasx = x;
            prek = prek + k;
            preb = preb + b;
        }

        if (infi) {
            cout << "-1\n";
        } else if (ans.empty()) {
            cout << "0\n";
        } else {
            cout << ans.size() << " ";
            for (int i = 0; i < ans.size(); i++)
                cout << ans[i] << " \n"[i == ans.size() - 1];
        }
        ans.clear();
        pos.clear();
    }
    return 0;
}

/*

4
2 3
1 2
1 -1
3 3
2 1
2 2
2 3
2 1
3 5
4 -1
3 2
1 -1
1 -2
1 -3


 */