题解归档 - cf498A

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

• 本地编号：cf498A
• 本地来源：problems/cf498A/idea.md
• 题目链接：https://codeforces.com/contest/498/problem/A
• 原始标题：CF498A Crazy Town

思路

CF498A Crazy Town

题意

平面上有 $n$ 条无限长直线，把平面分成若干连通区域（block）。家与大学各在一个 block 内（保证不在直线上）。一步可以从当前 block 走到与之共享非零长度公共边界的相邻 block（仅在交点处相邻、无公共线段则不算相邻）。求最少步数。

做法

每个 block 由「相对每条直线的半平面侧」唯一确定，用长度为 $n$ 的 01 串表示（+ 侧为 1，- 侧为 0）。

建图：对每条直线 $i$，求与其他直线的所有交点，在该线上按参数排序并去重。相邻交点之间的每个开线段（含两端无穷远射线）都是 $i$ 上的一段真实边界；取段中点，沿法向 $\pm\varepsilon$ 微扰得到两侧 block 的状态串，连无向边。

最短路：起点、终点状态已知，对偶图 BFS 即可。$n\le300$，区域数 $O(n^2)$，可过。

易错点

• 不能数「家与大学在直线两侧的不同条数」——必须按 block 邻接 BFS。
• getSt 内循环勿复用外层全局下标 i，否则会破坏建边循环。
• Linux 下勿用变量名 y1（与 <cmath> 冲突）。
• 交点重合的零长段不能建边。

验证

样例 + WSL 对拍 200 组（`n\le12$，坐标 $\le50$）。

代码

来源：problems/cf498A/solution.cpp

/* Author: likely
 * Time: 2026-06-08 04:25:22
**/
#include<bits/stdc++.h>
#define ll long long
#define ld long double
using namespace std;
const ld eps=1e-9;
const ll maxn=305;
ll n,i,j,k,hx,hy,ux,uy;
ll a[maxn],b[maxn],c[maxn];
string st,ed,cur;
map<string,vector<string>>g;
map<string,ll>dis;
queue<string>q;
ld refx,refy,dx,dy,nx,ny,ns;
struct pt{
    ld x,y,t;
};
vector<pt>ps;
bool cmpPt(pt u,pt v){
    return u.t<v.t;
}
string getSt(ld x,ld y){
    string s(n,'0');
    ll u;
    for(u=0;u<n;u++){
        ld v=(ld)a[u]*x+(ld)b[u]*y+(ld)c[u];
        s[u]=(v>0)?'1':'0';
    }
    return s;
}
void addE(string u,string v){
    if(u==v) return;
    for(stringw:g[u]) if(w==v) return;
    g[u].push_back(v);
    g[v].push_back(u);
}
void addSeg(ld t1,ld t2){
    if(t2-t1<eps) return;
    ld tm=(t1+t2)/2;
    ld px=refx+tm*dx,py=refy+tm*dy;
    addE(getSt(px+eps*nx,py+eps*ny),getSt(px-eps*nx,py-eps*ny));
}
int main(){
    cin>>hx>>hy>>ux>>uy>>n;
    for(i=0;i<n;i++) cin>>a[i]>>b[i]>>c[i];
    st=getSt(hx,hy);
    ed=getSt(ux,uy);
    if(st==ed){
        cout<<0<<endl;
        return 0;
    }
    for(i=0;i<n;i++){
        if(b[i]!=0){
            refx=0;
            refy=-(ld)c[i]/b[i];
        }else{
            refy=0;
            refx=-(ld)c[i]/a[i];
        }
        dx=(ld)b[i];
        dy=-(ld)a[i];
        nx=(ld)a[i];
        ny=(ld)b[i];
        ns=sqrt(nx*nx+ny*ny);
        nx/=ns;
        ny/=ns;
        ps.clear();
        for(j=0;j<n;j++){
            if(i==j) continue;
            ld det=(ld)a[i]*b[j]-(ld)a[j]*b[i];
            if(fabs(det)<eps) continue;
            ld px=((ld)b[i]*c[j]-(ld)b[j]*c[i])/det;
            ld py=((ld)a[j]*c[i]-(ld)a[i]*c[j])/det;
            pt p;
            p.x=px;
            p.y=py;
            p.t=(px-refx)*dx+(py-refy)*dy;
            ps.push_back(p);
        }
        sort(ps.begin(),ps.end(),cmpPt);
        vector<ld>ts;
        for(j=0;j<(ll)ps.size();j++){
            if(!ts.empty() and ps[j].t-ts.back()<eps) continue;
            ts.push_back(ps[j].t);
        }
        if(ts.empty()){
            addSeg(-1e12,1e12);
            continue;
        }
        addSeg(-1e12,ts[0]);
        for(j=0;j+1<(ll)ts.size();j++) addSeg(ts[j],ts[j+1]);
        addSeg(ts.back(),1e12);
    }
    dis[st]=0;
    q.push(st);
    while(!q.empty()){
        cur=q.front();
        q.pop();
        if(cur==ed) break;
        for(stringv:g[cur]){
            if(dis.count(v)) continue;
            dis[v]=dis[cur]+1;
            q.push(v);
        }
    }
    cout<<dis[ed]<<endl;
    return 0;
}