[BZOJ5328][扫描线][set]SDOI2018：物理实验

BZOJ5328

很明显的旋转坐标
然后用set维护扫描线离x轴最近的两条线段

要开long double

Code：

#include<bits/stdc++.h>
#define ll long long
#define db long double
using namespace std;
inline int read(){
	int res=0,f=1;char ch=getchar();
	while(!isdigit(ch)) {if(ch=='-') f=-f;ch=getchar();}
	while(isdigit(ch)) {res=(res<<1)+(res<<3)+(ch^48);ch=getchar();}
	return res*f;
}
const int N=100005;
int n,m,q[N];
db x[N][2],y[N][2],ins[N],val[N],p[N],X0,Y0,X1,Y1,L,x0;
inline bool cmp(int a,int b){return ((a>0)?x[a][0]:x[-a][1])<((b>0)?x[b][0]:x[-b][1]);}
struct line{
    int u;
    line(int _u=0):u(_u){}
    inline friend bool operator < (const line &a,const line &b){
        if(a.u==b.u)return false;
        db ya=(y[a.u][0]-y[a.u][1])/(x[a.u][0]-x[a.u][1])*(x0-x[a.u][0])+y[a.u][0];
        db yb=(y[b.u][0]-y[b.u][1])/(x[b.u][0]-x[b.u][1])*(x0-x[b.u][0])+y[b.u][0];
        return abs(ya)<abs(yb);
    }
};set<line>up,down;
void solve(){
    n=read(),m=0;
    for(int i=1;i<=n;i++){
        x[i][0]=read(),y[i][0]=read(),x[i][1]=read(),y[i][1]=read();
        ins[i]=sqrt((x[i][0]-x[i][1])*(x[i][0]-x[i][1])+(y[i][0]-y[i][1])*(y[i][0]-y[i][1]));
    }
    X0=read(),Y0=read(),X1=read(),Y1=read(),L=read();
    if(X0>X1)swap(X0,X1),swap(Y0,Y1);
    db dx=X1-X0,dy=Y1-Y0,len=sqrt(dx*dx+dy*dy),sin=dy/len,the=dx/len;
    for(int i=1;i<=n;i++){
        x[i][0]-=X0,x[i][1]-=X0,y[i][0]-=Y0,y[i][1]-=Y0;
        db t1,t2,t3,t4;
        t1=x[i][0]*the+y[i][0]*sin,t2=y[i][0]*the-x[i][0]*sin;
        t3=x[i][1]*the+y[i][1]*sin,t4=y[i][1]*the-x[i][1]*sin;
        x[i][0]=t1,y[i][0]=t2,x[i][1]=t3,y[i][1]=t4;
    }
    for(int i=1;i<=n;i++){
        if(x[i][0]>x[i][1])swap(x[i][0],x[i][1]),swap(y[i][0],y[i][1]);
        ins[i]/=(x[i][1]-x[i][0]);
    }
    for(int i=1;i<=n;i++)q[++m]=i,q[++m]=-i;
    sort(q+1,q+m+1,cmp);
    for(int i=1;i<=m;i++)val[i]=0;
    for(int i=1,u;i<=m;i++){
        if(q[i]>0){
            u=q[i];x0=p[i]=x[u][0];
            if(!up.empty())val[i]+=ins[up.begin()->u];
            if(!down.empty())val[i]+=ins[down.begin()->u];
            ((y[u][0]>0)?up:down).insert(line(u));
        }
        else{
            u=-q[i];x0=p[i]=x[u][1];
            if(!up.empty())val[i]+=ins[up.begin()->u];
            if(!down.empty())val[i]+=ins[down.begin()->u];
            ((y[u][0]>0)?up:down).erase(line(u));
        }
    }
    db res=0,ans=0,l=p[1]-L,r=p[1];int pl=1,pr=2;
    while(pr<=m){
        db dl=p[pl]-l,dr=p[pr]-r;
        if(dl>dr)res+=(val[pr]-val[pl])*dr,pr++,l+=dr,r+=dr;
        else if(dl<dr)res+=(val[pr]-val[pl])*dl,pl++,l+=dl,r+=dl;
        else res+=(val[pr]-val[pl])*dl,pl++,pr++,l+=dl,r+=dl;
        ans=max(ans,res);
    }
    printf("%.15Lf\n",ans);
}
int main(){
    for(int t=read();t--;)solve();
    return 0;
}