题解 CF598F 【Cut Length】

· · 题解

卡精度屑题，特别是26、27那两个hack的点，本地都跑过去了却被CF评测姬卡掉了，后来发现是精度开 10^{-8} 太小了会把相同的东西看成不同的，10^{-6} 才刚刚好卡过……

思想非常simple。我们回忆一下所谓的“射线法”（用来判断一个点是否在多边形内的那个算法），然后将其魔改一下，就变成了求出该直线与此多边形的所有交点，然后处在相邻两个交点间的线段便是其处于多边形内的部分。

因为 n 只有 1000，我们完全可以枚举每一条线段来找到它与直线的交点。很明显这些交点都在该直线上，那么我们把它们按照从直线的一段到另一端的顺序排序，然后就是找出第一个交点和第二个交点间的线段，第三个和第四个间的线段……

这是理论上的算法。真正实现起来会发现有很多要处理的：

  1. 关于重合的边的问题。

明显，如果边与直线重合，该边是一定要计入的；于是我们单独开一个数组维护所有这样的边，然后将这样的边与上文所述线段求一个并即可。

  1. 关于直线何时与边有交的问题

当直线与边不交在一些奇奇怪怪的位置之前，这实际上是很simple的；但是的确会出现奇奇怪怪的位置，比如说直线与一个角相交（这时需要判断直线是穿过了角进入了多边形（这时就贡献了一个交点），还是只是擦过去并没有真正进去），或是直线与边重合（这时还是上文所述两种情况，进去或是没进去）。这玩意需要好好讨论一下，如果不想讨论也可以直接看代码，里面有注释。

在处理这情形2的时候，最好把所有 180^{\circ} 的角都删掉，不然可能会增加讨论量。

最终时间复杂度 O(nm\log n)，因为区间并是 O(n\log n) 的。

代码（最后附有三组我绞尽脑汁构造出来卡掉我自己的数据，如果实在不知道什么错也可以拿去玩玩）：

#include<bits/stdc++.h>
using namespace std;
#define double long double
const double eps=1e-6;
int cmp(double x){
    if(x>eps)return 1;
    if(x<-eps)return -1;
    return 0;
}
struct Vector{
    double x,y;
    Vector(){}
    Vector(double X,double Y){x=X,y=Y;}
    friend Vector operator +(const Vector &u,const Vector &v){return Vector(u.x+v.x,u.y+v.y);}
    friend Vector operator -(const Vector &u,const Vector &v){return Vector(u.x-v.x,u.y-v.y);}
    friend Vector operator *(const Vector &u,const double &v){return Vector(u.x*v,u.y*v);}
    friend Vector operator /(const Vector &u,const double &v){return Vector(u.x/v,u.y/v);}
    friend double operator &(const Vector &u,const Vector &v){return u.x*v.y-u.y*v.x;}//cross times
    friend double operator |(const Vector &u,const Vector &v){return u.x*v.x+u.y*v.y;}//point times
    double operator ~()const{return sqrt(x*x+y*y);}//the modulo of a vector
    double operator !()const{return atan2(y,x);}//the angle of a vector
    friend bool operator <(const Vector &u,const Vector &v){return cmp(u.x-v.x)?u.x<v.x:u.y<v.y;}
    friend bool operator ==(const Vector &u,const Vector &v){return !cmp(u.x-v.x)&&!cmp(u.y-v.y);}
    void read(){scanf("%Lf%Lf",&x,&y);}
    void print()const{printf("(%Lf,%Lf)",x,y);}
}p[1010];
Vector read(){Vector x;x.read();return x;}
typedef Vector Point;
struct Line{
    Point x,y;
    Vector z;
    Line(){}
    Line(Point X,Point Y){x=X,y=Y,z=Y-X;}
    void print()const{x.print(),y.print();}
    friend Point operator &(const Line &u,const Line &v){return u.x+u.z*((v.z&(u.x-v.x))/(u.z&v.z));}
    friend int operator &(const Line &u,const Point &v){return cmp((v-u.x)&(v-u.y));}//point v is on which side of line u
};
typedef Line Segment;
int n,m;
vector<Segment>u;
vector<Point>v,w;
vector<int>b;
bool on[1010];
double calc(Line l){
    u.clear(),v.clear(),memset(on,false,sizeof(on));
    for(int i=0;i<n;i++){
        if(!cmp((p[i]-p[(i+1)%n])&l.z)){//two lines parallel
            if(cmp(l.z&(p[i]-l.x)))continue;
            u.emplace_back(p[i],p[(i+1)%n]);//two lines coincide
            Segment tmp(p[i],p[(i+1)%n]);if((tmp&p[(i+n-1)%n])!=(tmp&p[(i+2)%n]))v.push_back(p[i]);
            //the line crossed the border at the coincided edge
            continue;
        }
        Point x=Line(p[i],p[(i+1)%n])&l;//if not parallel, this is the intersection point
        if(x==p[i]){on[i]=true;continue;}
        if(x==p[(i+1)%n]){on[(i+1)%n]=true;continue;}//if intersection point is concide with one endpoint of the segment,consider it specially
        if(cmp((x-p[i])|(x-p[(i+1)%n]))==1)continue;//intersection is not on the segment
        v.push_back(x);
    }
    for(int i=0;i<n;i++){//this loop only consider points exactly on the line
        if(!on[i])continue;
        if(on[(i+n-1)%n]||on[(i+1)%n])continue;//if this point is endpoint of a coinciding edge, do not bother as we've considered it previously
        Point x=(l.x==p[i]?l.y:l.x);//find one point on the line which do not coincide with the current point
        Segment A(p[(i+n-1)%n],p[i]);bool a=((A&x)!=(A&p[(i+1)%n]));
        Segment B(p[(i+1)%n],p[i]);bool b=((B&x)!=(B&p[(i+n-1)%n]));
        if(a==b)v.push_back(p[i]);//cross the border.
    }
    sort(v.begin(),v.end()),w=v;
    for(auto i:u)w.push_back(i.x),w.push_back(i.y);
    sort(w.begin(),w.end());
    b.assign(w.size(),0);
    for(int i=0;i<v.size();i+=2){
        int l=lower_bound(w.begin(),w.end(),v[i])-w.begin();
        int r=lower_bound(w.begin(),w.end(),v[i+1])-w.begin();
        b[l]++,b[r]--;
    }
    for(int i=0;i<u.size();i++){
        int l=lower_bound(w.begin(),w.end(),u[i].x)-w.begin();
        int r=lower_bound(w.begin(),w.end(),u[i].y)-w.begin();
        if(l>r)swap(l,r);
        b[l]++,b[r]--;
    }
    for(int i=1;i<b.size();i++)b[i]+=b[i-1];
    double ret=0;
    for(int i=0;i+1<b.size();i++)if(b[i])ret+=~(w[i+1]-w[i]);
    return ret;
}
int N;
int main(){
    scanf("%d%d",&N,&m);
    for(int i=0;i<N;i++){
        p[n].read();
        if(n>=2&&cmp((p[n]-p[n-1])&(p[n]-p[n-2]))==0)n--,p[n]=p[n+1];//eliminating those 180-degree angles.
        n++;
    }
    if(n>=3&&cmp((p[0]-p[n-1])&(p[0]-p[n-2]))==0)n--;
    if(n>=3&&cmp((p[1]-p[0])&(p[1]-p[n-1]))==0){for(int i=0;i+1<n;i++)p[i]=p[i+1];n--;}
    while(m--)printf("%.10Lf\n",calc(Line(read(),read())));
    return 0;
}
/*
12 5
-1 0
-2 1
-1 2
0 1
1 2
2 1
1 0
2 -1
1 -2
0 -1
-1 -2
-2 -1
-2 -1 -1 0
-2.01 -1 -1.01 0
-1.99 -1 -0.99 0
-1 0 1 0
1 2 2 1

8 4
0 0
0 1
0 2
1 2
2 2
2 1
1 1
1 0
1 0 1 1
0 1 1 1
0 0 1 1
1 0 2 1

6 3
0 0
0 1
0 2
1 1
2 0
1 0
0 0 1 1
2 0 0 2
2 0 0 1
*/