题解：P3194 [HNOI2008] 水平可见直线

· · 题解

0.前言

省流：蒟蒻学习计算几何,rp++
蒟蒻过蒻，题解中会出现许多蒟蒻趋势的心路历程，大佬勿入
感谢 desmos 对计算几何的大力支持

1.思路

既然是计算几何题，必然和计算以及几何有关了！
哎，这不李超树吗
不难想到这样一条性质：

性质1：直线交点两端的直线如果都能看到，必定斜率小的在左，斜率大的在右

有点抽象是不是？
不妨打开 desmos，自己逝世。
这里放一张简单的图1

如图，我们还可以得到第二条性质：

性质2：可以看到的直线的斜率单调递增

这个性质，用性质1推广一下就可得了
然而 sort 后算交点时 RE 了，为什么呢？
由于我们不是很聪明，我们一开始并没有想到斜率相等
于是我们先手造一个图2

发现其实只要特判一手即可
可恶啊啊啊啊啊啊啊
象征性的写一个性质

性质3：斜率相等的直线只有与x轴交点最高的直线可能被看到

然后再写两个解题用的性质

性质4：可以看到的直线按斜率单调递增排列时，相邻直线的交点横坐标必定从小到大
性质5：直线按斜率单调递增排列时，如果相邻直线的交点横坐标从小到大，则这些直线可以被看到，否则不能被看到（就是性质4的逆命题）

也就是说，可以用单调栈维护直线的交点坐标了。
为什么满足以上性质就可以了呢？
BDFS 啊 ::::info[这是deepseek给出的解释] 因为 LaTeX 炸了导致题解被打回QAQ :::: ::::info[这是窝给出的解释] 先构造一个图，然后按性质逐个反证即可 :::: 这样，你就可以 AC 了……吗？
众所周知，计算几何中有一位幻神，名曰浮点数
所以我们手动造出图3
由于浮点数飞来飞去的特殊性质，有一定可能这个交点不会 ==0
然后你会得到60pts的一种可能
要是开放数据下载这题早过了
所以接下来是

2.代码

一些细节，见代码

#include<bits/stdc++.h>
#define sj(q,z) double((l[z].b-l[q].b)*1.0)/(l[q].a-l[z].a)
using namespace std;
const int N=5e4+5;
const double zuzong=1e-12;//~~生动形象地说明了祖宗的重要性~~ 
struct l_n{
    double a,b;//题面意思，开double的原因是后面可能算浮点 
    int x;//记录第几条，不要像蒟蒻一样直接sort完就输出了 
}l[N];
bool xl(l_n x,l_n y){
    return x.a==y.a?x.b>y.b:x.a<y.a;
}
bool k[N];
vector<int> vc;//单调栈 
int n;
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin>>n;
    for(int i=1;i<=n;i++)cin>>l[i].a>>l[i].b,l[i].x=i;
    sort(l+1,l+n+1,xl);
    vc.push_back(1);
    for(int i=2;i<=n;i++){
        if(l[i].a==l[i-1].a)continue;//特判性质3
        while(vc.size()>1&&sj(vc[vc.size()-1],vc[vc.size()-2])+zuzong>sj(vc[vc.size()-1],i))vc.pop_back();
        //蒟蒻这个条件调了好久……
        vc.push_back(i);
    }
    for(int i=0;i<vc.size();i++)k[l[vc[i]].x]=1;//血的教训啊……
    for(int i=1;i<=n;i++)if(k[i])cout<<i<<' '; 
    return 0;
}

3.后记

当最后一个测试点终于亮起绿色的 AC 时，本蒟蒻颤抖着关掉了卡了三天浮点精度的 desmos 页面。屏幕上残留的直线交点轨迹，像极了这段代码之路的心电图——时而陡峭如未特判的同斜率直线，时而平缓如单调栈里被弹出的旧梦。

原来浮点误差才是真正的祖宗啊！

那些对着性质1反复画图的时刻，那些因为没判斜率相等而 RE 到怀疑人生的提交记录，最终都化作代码里那个卑微的 zuzong=1e-12。

或许这就是计算几何的浪漫：你以为在写数学，其实在写哲学；你以为在调精度，其实在调人生。

特别鸣谢：

desmos：您比蒟蒻的脑子更懂几何（甚至自动标注了交点坐标）
洛谷讨论区?：60pts 的血泪史教会我，浮点数的世界没有"差不多"
伟大的题解大人：不要试图把交点坐标存起来，因为交点随时可能变化，计算几何的祖宗实在太多了

最后，谨以此题解献给所有被浮点数暴打的OIer——愿我们的 rp++，愿我们的斜率永远单调递增。

（完）

P.S. 下次再写计算几何题我就是__（填空题，4分） :::info[警示后入]

不符合推荐标准。原因是：【中文】与【英文、数字或公式】之间应以半角空格隔开；数学公式（运算式、运算符、数学推导、参与运算的常数、作为变量的字母等）应使用 LaTeX。。

不符合推荐标准。原因是：句子末尾应添加句号，且全文使用的句号应一致。。

不符合推荐标准。原因是：非数学公式（一般英文单词、题目名、算法名、人名等）不应使用 LaTeX。