题解归档 - cf104114B

本文由 cf-code 本地题解库自动归档；公开内容以本地 AC/验证版本为准。

• 本地编号：cf104114B
• 本地来源：problems/cf104114B/idea.md
• 题目链接：https://codeforces.com/gym/104114/problem/B
• 原始标题：cf104114B - Birthday Cake

思路

cf104114B - Birthday Cake

One side of the cut must contain no strawberries. For a direction vector u, the strawberry-free side can be written as

u · x > max_s(u · s).

So a chocolate point p is included for exactly those directions u satisfying

u · (p - s) > 0 for every strawberry s.

For a fixed vector p-s, this is an open semicircle of directions: within 90° of p-s. Intersect the m open semicircles for one chocolate; if the intersection is non-empty, it contributes one or two angle intervals on [0,2π).

The answer is the maximum number of chocolate intervals covering the same angle. Sweep events on the circle.

This avoids enumerating chocolates against hull edges explicitly and is safe because m <= 100, n <= 50000.

Complexity: O(n m log m + n log n).

代码

来源：problems/cf104114B/solution.cpp

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

const double PI=acos(-1.0);
const double TAU=2.0*PI;
const double EPS=1e-12;

struct Pt{
    double x,y;
};

double norm_ang(double x){
    x=fmod(x,TAU);
    if(x<0) x+=TAU;
    return x;
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n,m;
    cin>>n>>m;
    vector<Pt> c(n),s(m);
    for(auto &p:c) cin>>p.x>>p.y;
    for(auto &p:s) cin>>p.x>>p.y;

    vector<pair<double,int>> all;
    all.reserve(2*n+5);

    auto add_interval=[&](double l,double r){
        if(r-l<=EPS) return;
        all.push_back({l,+1});
        all.push_back({r,-1});
    };

    for(auto p:c){
        vector<pair<double,int>> ev;
        ev.reserve(2*m);
        int initial=0;
        for(auto q:s){
            double th=atan2(p.y-q.y,p.x-q.x);
            double l=norm_ang(th-PI/2.0);
            double r=norm_ang(th+PI/2.0);
            if(l<r){
                ev.push_back({l,+1});
                ev.push_back({r,-1});
            }else{
                initial++;
                ev.push_back({r,-1});
                ev.push_back({l,+1});
            }
        }

        sort(ev.begin(),ev.end(),[](auto a,auto b){
            if(fabs(a.first-b.first)>EPS) return a.first<b.first;
            return a.second<b.second;
        });

        int cur=initial;
        double last=0;
        for(int i=0;i<(int)ev.size();){
            double x=ev[i].first;
            if(x-last>EPS&&cur==m) add_interval(last,x);
            while(i<(int)ev.size()&&fabs(ev[i].first-x)<=EPS){
                cur+=ev[i].second;
                i++;
            }
            last=x;
        }
        if(TAU-last>EPS&&cur==m) add_interval(last,TAU);
    }

    sort(all.begin(),all.end(),[](auto a,auto b){
        if(fabs(a.first-b.first)>EPS) return a.first<b.first;
        return a.second>b.second;
    });

    int ans=0,cur=0;
    double last=0;
    for(int i=0;i<(int)all.size();){
        double x=all[i].first;
        if(x-last>EPS) ans=max(ans,cur);
        while(i<(int)all.size()&&fabs(all[i].first-x)<=EPS){
            cur+=all[i].second;
            i++;
        }
        last=x;
    }
    if(TAU-last>EPS) ans=max(ans,cur);

    cout<<ans<<"\n";
    return 0;
}