最短路（数据处理）：HDU 5817 Ice Walls

Have you ever played DOTA? If so, you may know the hero, Invoker. As one of the few intelligence carries, Invoker has 10 powerful abilities. One of them is the Ice Wall: Invoker generates a wall of solid ice directly in front of him, and the bitter cold emanating from it greatly slows nearby enemies and deals damage each second.

Now consider the map as a plane. You are now at point s, and want to move to point t. But Invoker has placed N ice walls on the map. Your moving speed is 1 per second, but you need k seconds to pass an ice wall. Time is precious, you must get to point t as quickly as possible. What's the minimum time you need?

For convenience, you can assume that all ice walls are segments (no width) either parallel to X-axis or to Y-axis. Segments are strictly disjoint (have no common point). Point s and t are not on any segment (have no common point).

You will not be slowed when pass the end point of a segment or walk along a segment.

 

Input

The input begins with an integer T, indicating the number of test cases. For each case, the first line is two integers N and k (1 <= N <= 500, 0 <= k <= 10^8), indicating the number of segments and the time needed to pass an ice wall. Next N lines, each have four integers x1, y1, x2, y2, indicating two end points of a segment, (x1, y1) and (x2, y2). Next line has two integers xs and ys, representing the coordinates of starting point s. The last line also has two integers xt and yt, representing the coordinates of target point t. For every point, |x| and |y| <=  108.

 

Output

For each case, output one line containing the minimum time in second needed to get to t from s. The answer should be given within an absolute or relative error of  10−6.

 

Sample Input

3
1 1
1 0 1 2
0 0
2 0
1 1
1 -2 1 2
0 0
2 0
1 3
1 -2 1 2
0 0
2 0

Sample Output

2.000000
3.000000
4.472136
　　
　　这道题还是有些挑战的，可以一眼看出是最短路，但如何处理出点对的直接路径？
　　考虑极角排序，我不会，就用三角函数的sin和cos代替，然后用bit维护，可以做到N²logN。

#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>
#include <cmath>
using namespace std;
const double eps=1e-10;
const int N=1010,M=4000010;

struct Node{int x,y,tp;}point[N],s,t,tmp;
struct Data{Node t;int id;double k,d;}st[N];
int hsh[2*N],bit[2*N],csh,top;double G[N][N];

double Dis(Node a,Node b){
    return sqrt(1.0*(a.x-b.x)*(a.x-b.x)+1.0*(a.y-b.y)*(a.y-b.y));
}

double K1(Node b){return 1.0*(b.x-tmp.x)/Dis(tmp,b);}
double K2(Node b){return 1.0*(b.y-tmp.y)/Dis(tmp,b);}

int Rk1(int tp){return tp==4?1:tp==3?3:2;}
int Rk2(int tp){return tp==2?1:tp==1?3:2;}

bool cmp1(Data p,Data q){ 
    Node a=p.t,b=q.t;
    if(fabs(p.k-q.k)>0)return q.k-p.k>=eps;
    if(a.tp==4&&b.tp==4)return q.d-p.d>=eps;
    if(a.tp==3&&b.tp==3)return p.d-q.d>=eps;
    return Rk1(a.tp)<Rk1(b.tp);
}

bool cmp2(Data p,Data q){ 
    Node a=p.t,b=q.t;
    if(fabs(p.k-q.k)>0)return p.k<q.k;
    if(a.tp==2&&b.tp==2)return p.d<q.d;
    if(a.tp==1&&b.tp==1)return p.d>q.d;
    return Rk2(a.tp)<Rk2(b.tp);
}
int Query(int x,int y){int ret=0;
    x=lower_bound(hsh+1,hsh+csh+1,x)-hsh-1;
    while(x){ret-=bit[x];x-=x&(-x);}
    y=lower_bound(hsh+1,hsh+csh+1,y)-hsh;
    while(y){ret+=bit[y];y-=y&(-y);}
    return ret;
}

void Add(int x,int d){
    x=lower_bound(hsh+1,hsh+csh+1,x)-hsh;
    while(x<=csh)bit[x]+=d,x+=x&(-x);
}

int tot,n,ice,T;
void Solve1(int p){
    tmp=point[p];top=0;
    for(int i=1;i<=tot;i++){
        Node b=point[i];if(tmp.y<=b.y)continue;
        st[++top]=(Data){b,i,K1(b),Dis(tmp,b)};
    }sort(st+1,st+top+1,cmp1);
    memset(bit,0,sizeof(bit));
    for(int i=1;i<=top;i++){
        Data b=st[i];Node c=b.t;
        if(c.tp==4)Add(c.y,-1);
        G[b.id][p]+=ice*Query(c.y,tmp.y);
        G[p][b.id]+=ice*Query(c.y,tmp.y);
        if(c.tp==3)Add(c.y,1);
    }
}

void Solve2(int p){
    tmp=point[p];top=0;
    for(int i=1;i<=tot;i++){
        Node b=point[i];if(tmp.x<=b.x)continue;
        st[++top]=(Data){b,i,K2(b),Dis(tmp,b)};
    }sort(st+1,st+top+1,cmp2);
    memset(bit,0,sizeof(bit));
    for(int i=1;i<=top;i++){
        Data b=st[i];Node c=b.t;
        if(c.tp==2)Add(c.x,-1);
        G[b.id][p]+=ice*Query(c.x,tmp.x);
        G[p][b.id]+=ice*Query(c.x,tmp.x);
        if(c.tp==1)Add(c.x,1);
    }
}

int vis[N];double dis[N];
double Dij(int s,int t){
    for(int i=0;i<N;i++)
    dis[i]=1e20,vis[i]=0;dis[s]=0;
    for(int i=1,p;i<=tot;i++){p=0;
        for(int j=1;j<=tot;j++)
            if(!vis[j]&&dis[p]>dis[j])p=j;
        vis[p]=true;
        for(int j=1;j<=tot;j++)
            dis[j]=min(dis[j],dis[p]+G[p][j]);        
    }
    return dis[t];
}

void Initial(){
    memset(G,0,sizeof(G));
    tot=csh=0;
}

int main(){
    scanf("%d",&T);
    while(T--){
        scanf("%d%d",&n,&ice);Initial();
        for(int i=1,x1,y1,x2,y2;i<=n;i++){
            scanf("%d%d%d%d",&x1,&y1,&x2,&y2);
            hsh[++csh]=x1;hsh[++csh]=x2;
            hsh[++csh]=y1;hsh[++csh]=y2;
            if(x1==x2&&y1==y2)continue;
            if(x1==x2){
                if(y1>y2)swap(y1,y2);
                point[++tot]=(Node){x1,y1,1};
                point[++tot]=(Node){x2,y2,2};
            }
            if(y1==y2){
                if(x1>x2)swap(x1,x2);
                point[++tot]=(Node){x1,y1,3};
                point[++tot]=(Node){x2,y2,4};
            }
        }
        
        scanf("%d%d",&s.x,&s.y);
        scanf("%d%d",&t.x,&t.y);

        hsh[++csh]=s.x;hsh[++csh]=s.y;
        hsh[++csh]=t.x;hsh[++csh]=t.y;
        
        sort(hsh+1,hsh+csh+1);
        csh=unique(hsh+1,hsh+csh+1)-hsh-1;
            
        point[++tot]=(Node){s.x,s.y,0};
        point[++tot]=(Node){t.x,t.y,0};
        
        for(int i=1;i<=tot;i++)Solve1(i);
        for(int i=1;i<=tot;i++)Solve2(i);    
        
        for(int i=1;i<=tot;i++)
            for(int j=1;j<=tot;j++)
                G[i][j]+=Dis(point[i],point[j]);
        printf("%.6lf\n",Dij(tot-1,tot));
    }
    return 0;
}

　　WA在求dis的平方上了，注意会爆int。

附上数据生成器：

#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>
#include <cstdlib>
#include <ctime>
using namespace std;
int G[1010][1010],h[1010];
int main(){
    srand(time(NULL));
    int T=1,n=500,w=1000;
    printf("%d\n",T);
    while(T--){
        printf("%d %d\n",n,rand()%w);
        int x,y,a,b,l;
        for(int i=0;i<w;i++){
            h[i]=rand()*rand()%100000000;
            if(rand()%2)h[i]*=-1;
        }
        sort(h,h+w);
        memset(G,0,sizeof(G));
        for(int i=1;i<=n;i++){
            while(true){
                x=rand()%w;y=rand()%w;
                while(G[x][y])x=rand()%w,y=rand()%w;
                if(rand()%2){
                    a=x;l=0;
                    while(y+l+1<=w&&G[x][y+l]==0)l++;
                    if(l==1)continue;b=y+rand()%(l-1)+1;
                }
                else{
                    b=y;l=0;
                    while(x+l+1<=w&&G[x+l][y]==0)l++;
                    if(l==1)continue;a=x+rand()%(l-1)+1;
                }
                for(int j=x;j<=a;j++)
                    for(int k=y;k<=b;k++)
                        G[j][k]=1;
                printf("%d %d %d %d\n",h[x],h[y],h[a],h[b]);
                break;        
            }
        }
        x=rand()%w;y=rand()%w;
        while(G[x][y])x=rand()%w,y=rand()%w;
        printf("%d %d\n",h[x],h[y]);G[x][y]=1;
        x=rand()%w;y=rand()%w;
        while(G[x][y])x=rand()%w,y=rand()%w;
        printf("%d %d\n",h[x],h[y]);
    }
    return 0;
}