我使用的是C++20，并使用了大量现代化C++语法，可能与C++11不同，注意更改

关于卡常

预处理出所有向量的角度
排序常数极大，需要事先将所有线段极角排序，二分时直接遍历所有线段并把编号小于 maxID 的取出来
对于 long double，尽量避免除法运算，因此在选点时能用乘代替除就用乘代替除

我的代码中点选择了

CPP

for(int i=0;i<n;++i){
    int x,t1,t2; read(x,t1,t2);
    double y1=(t1-EPS)/x, y2=(t2+EPS)/x;
    org.emplace_back(i,line(Point(0,y1),Point(1,y1-x)));
    org.emplace_back(i,line(Point(1,y2-x),Point(0,y2)));
}

如果你是和我一样，对于向量的点乘和叉乘使用的是：

CPP

Vec operator+(Vec u, Vec v) { return {u.x + v.x, u.y + v.y}; }      //  向量加向量
Vec operator-(Vec u, Vec v) { return {u.x - v.x, u.y - v.y}; }      //  向量减向量
double operator*(Vec u, Vec v) { return u.x * v.x + u.y * v.y; }    //  点乘
double operator^(Vec u, Vec v) { return u.x * v.y - u.y * v.x; }    //  叉乘

这边建议将此类函数定义在类中，这样将显著减少时间花费

这里给出我的代码：

CPP

struct Point {
    double x, y;

    constexpr Point operator-() const { return {-x,-y}; }
    constexpr Point operator+(const Point &rhs) const { return {x + rhs.x, y + rhs.y}; }    //  向量加向量
    constexpr Point operator-(const Point &rhs) const { return {x - rhs.x, y - rhs.y}; }    //  向量减向量
    constexpr Point operator*(double k) const { return {x * k, y * k}; }                    //  数乘
    constexpr Point operator/(double k) const { return {x / k, y / k}; }                    //  除法
    constexpr double operator*(Point rhs) const { return x * rhs.x + y * rhs.y; }           //  点乘
    constexpr double operator^(Point rhs) const { return x * rhs.y - y * rhs.x; }           //  叉乘
    constexpr double len() { return sqrt(x * x + y * y); }                                  //  向量长度
    constexpr Point norm(){ return (*this)/len(); }                                         //  向量归一化
    constexpr Point pnorm(){ return norm()*(x<0?-1:1); }                                    //  指向x轴正半轴的归一化向量
};

关于卡精度

此时一般情况是 test 1 和 test 5只能对一个，我的情况是当我使用 ge（大于等于）进行半平面交的时候会 WA on test 1，换成 gt（大于）会 WA on test 5

解决措施：将 y1,y2 改成 y1-EPS, y2+EPS, 并且将边界从 0 改为 EPS

在我的代码中表现为：

CPP

vector<PIL>org={
    {-1, line(Point(-INF,EPS),Point(-EPS,EPS))},
    {-1, line(Point(-EPS,EPS),Point(-EPS,INF))},
    {-1, line(Point(-EPS,INF),Point(-INF,INF))},
    {-1, line(Point(-INF,INF),Point(-INF,EPS))}
};

本题卡常+卡精度，下面提出解决措施

讨论操作

关于卡常

关于卡精度

回复

相关推荐

本题卡常+卡精度，下面提出解决措施