提出 #72189581

---

ソースコード 拡げる

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> pll;

// 计算两个线段是否相交
bool doIntersect(pll p1, pll p2, pll q1, pll q2) {
    auto cross = [](pll a, pll b, pll c) -> ll {
        return (b.first - a.first) * (c.second - a.second) - (b.second - a.second) * (c.first - a.first);
    };
    
    ll d1 = cross(p1, p2, q1);
    ll d2 = cross(p1, p2, q2);
    ll d3 = cross(q1, q2, p1);
    ll d4 = cross(q1, q2, p2);
    
    // 如果线段相交或端点重合，则不能同时放风筝
    if (((d1 > 0 && d2 < 0) || (d1 < 0 && d2 > 0)) && 
        ((d3 > 0 && d4 < 0) || (d3 < 0 && d4 > 0))) {
        return true;
    }
    
    // 检查端点是否在线段上
    if (d1 == 0 && min(p1.first, p2.first) <= q1.first && q1.first <= max(p1.first, p2.first) &&
        min(p1.second, p2.second) <= q1.second && q1.second <= max(p1.second, p2.second)) {
        return true;
    }
    
    if (d2 == 0 && min(p1.first, p2.first) <= q2.first && q2.first <= max(p1.first, p2.first) &&
        min(p1.second, p2.second) <= q2.second && q2.second <= max(p1.second, p2.second)) {
        return true;
    }
    
    if (d3 == 0 && min(q1.first, q2.first) <= p1.first && p1.first <= max(q1.first, q2.first) &&
        min(q1.second, q2.second) <= p1.second && p1.second <= max(q1.second, q2.second)) {
        return true;
    }
    
    if (d4 == 0 && min(q1.first, q2.first) <= p2.first && p2.first <= max(q1.first, q2.first) &&
        min(q1.second, q2.second) <= p2.second && p2.second <= max(q1.second, q2.second)) {
        return true;
    }
    
    return false;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    
    ll N;
    cin >> N;
    vector<pll> points(N);
    for (ll i = 0; i < N; i++) {
        cin >> points[i].first >> points[i].second;
    }
    
    // 贪心算法：按某种顺序选择尽可能多的不冲突的风筝
    // 使用图论方法：构建冲突图，然后求最大独立集
    
    // 由于N很大，不能构建完整的图
    // 转换思路：将问题转化为区间调度问题
    
    // 计算每条线段的斜率和截距，用于快速判断相交
    vector<pair<double, ll>> slopes(N);
    for (ll i = 0; i < N; i++) {
        // 线段从(Ai, 0)到(Bi, 1)，斜率为1/(Bi-Ai)
        // 为了便于比较，我们使用Ai-Bi作为排序依据
        slopes[i] = {points[i].second - points[i].first, i};
    }
    
    // 按斜率排序
    sort(slopes.begin(), slopes.end());
    
    // 贪心选择：选择尽可能多的不相交线段
    vector<bool> used(N, false);
    ll count = 0;
    
    for (ll i = 0; i < N; i++) {
        ll idx = slopes[i].second;
        if (used[idx]) continue;
        
        bool conflict = false;
        // 检查与已选线段是否冲突
        for (ll j = 0; j < i; j++) {
            ll prev_idx = slopes[j].second;
            if (used[prev_idx]) {
                // 检查线段是否相交
                pll p1 = {points[idx].first, 0};
                pll p2 = {points[idx].second, 1};
                pll q1 = {points[prev_idx].first, 0};
                pll q2 = {points[prev_idx].second, 1};
                
                if (doIntersect(p1, p2, q1, q2)) {
                    conflict = true;
                    break;
                }
            }
        }
        
        if (!conflict) {
            used[idx] = true;
            count++;
        }
    }
    
    cout << count << endl;
    return 0;
}

提出情報

ジャッジ結果