ncpc 2016 Keeping the Dogs Apart

布满荆棘的人生 2022-05-28 09:22 133阅读 0赞

题目：  
Despite the unfortunate incident last summer, which resulted in ten little puppies, you have been tasked with taking care of your neighbors’ dogs again. Shadow and Lydia may be very cute mutts, but this year you have strict instructions to walk them one by one. However, you have other things to do during the summer than walking dogs! Like playing fetch and solving programming problems! It seems terribly inefficient to walk the dogs one at a time.  
Shadow and Lydia have a particular walk they each prefer and know by heart. If you just let them out, they will follow their favorite walk, eventually ending up in their respective doghouses. Problem solved!

Sadly, you realize that if you just let both dogs out at the same time and let them do their walks on their own, they might get too close to each other. If they get too close, they will leave their favorite walk to “have some fun’’ and you are not sure you can find good homes for any more puppies. To ensure this does not happen, you need to calculate the minimum distance between the dogs when they are out walking on their own.

Both dogs start at the same time and keep exactly the same pace. Immediately after a dog arrives at its doghouse it stays inside and goes to sleep, so we no longer need to worry about the distance to the other dog, even though the other dog may still walk for a while longer. Note that a dog is still awake at the exact moment of entering its house and falls asleep immediately after entering.

Input

The first line of input consists of an integer nn (2≤n≤1000002≤n≤100000), the number of points describing the walk of Shadow. The next nn lines contain 22 integers each, giving the xx and yy coordinates of Shadow’s walk. Two consecutive points in the walk always differ in at least one coordinate. All coordinates are non-negative and at most 1000010000. Similarly, the next line contains an integer mm (2≤m≤1000002≤m≤100000), the number of points describing the walk of Lydia. The next mm lines describe its walk in the same format as for Shadow.

Output

Output the minimum distance between the two dogs during their walks. The numbers should be accurate to an absolute or relative error of at most 10−410−4.

Sample Input 1  
2  
0 0  
10 0  
2  
30 0  
15 0  
Sample Output 1  
10  
Sample Input 2  
5  
10 0  
10 8  
2 8  
2 0  
10 0  
9  
0 8  
4 8  
4 12  
0 12  
0 8  
4 8  
4 12  
0 12  
0 8  
Sample Output 2  
1.414213562373

题意：给出两只狗行走的折线段，求两条狗在行走过程中，两只狗的最短距离！

题解：  
第一步：以两条狗不切换路线为单位分步求  
第二步：一只狗从p到p+▲p,另一只狗从q到▲q可以等价为一个不动点p,另一个动点q从q到q+▲q-▲p

具体代码如下：  
注意要使用高精度\_\_float128,用double会卡精度

#include<iostream>
    #include<stdio.h>
    #include<algorithm>
    #include<cstring>
    #include<cmath>
    using namespace std;
    
    const __float128 esp=1e-10;
    
    __float128 fabsq(__float128 x) {
        return max(x,-x);
    }
    
    int dcmp(__float128 x){
        if(fabsq(x)<esp)return 0;
        else return x<0?-1:1;
    }
    
    class P{
        public:
            __float128 x,y;
            P(__float128 x=0,__float128 y=0):x(x),y(y){}
            friend __float128 Dot(P A,P B){
                return A.x*B.x+A.y*B.y;
            }
            friend __float128 length(P A){
                return (__float128)sqrt((double)Dot(A,A));
            }
            friend P operator- (P A,P B) { return P(A.x-B.x,A.y-B.y); }
            friend P operator+ (P A,P B) { return P(A.x+B.x,A.y+B.y); }
            friend P operator* (P A,__float128 p) { return P(A.x*p,A.y*p); }
            friend P operator/ (P A,__float128 p) { return P(A.x/p,A.y/p); }
            friend bool operator< (const P& a,const P& b) {
       return dcmp(a.x-b.x)<0 ||(dcmp(a.x-b.x)==0&& dcmp(a.y-b.y)<0 );}
    };
    
    bool operator==(const P& a,const P& b){
        return dcmp(a.x-b.x)==0&&dcmp(a.y-b.y)==0;
    }
    
    typedef P V;
    __float128 Cross(V A,V B) {
       return A.x*B.y - A.y*B.x;}
    
    __float128 DistanceToSegment(P p,P A,P B) {
        if (A==B) return length(p-A);
        V v1 = B-A, v2 = p-A, v3 = p - B;
        if (dcmp(Dot(v1,v2))<0) return length(v2);
        else if (dcmp(Dot(v1,v3))>0 ) return length(v3);
        else return fabsq(Cross(v1,v2) ) / length(v1);
    }
    
    P read_point(){
        double x,y;
        scanf("%lf%lf",&x,&y);
        P a=P(x,y);
        return a;
    }
    const int MAXN=120000;
    P a[MAXN],b[MAXN];
    __float128 t1[MAXN],t2[MAXN];
    int n,m;
    int main(){
        cin>>n;
        for(int i=1;i<=n;++i){
            a[i]=read_point();
        }
        for(int i=2;i<=n;++i){
            t1[i]=length(a[i]-a[i-1])+t1[i-1];//为了方便之后记录走到哪了，所以累加
        }
        cin>>m;
        for(int i=1;i<=m;++i){
            b[i]=read_point();
        }
        for(int i=2;i<=m;++i){
            t2[i]=length(b[i]-b[i-1])+t2[i-1];
        }
        int l1=1,l2=1;
        __float128 nowt=0;
        P A(b[1]-a[1]);
        __float128 ans=length(A),t;
    
    **//关键代码！！！！！**
    ---------------
    
        while(l1<n&&l2<m){
            if (t1[l1+1]<t2[l2+1]) {
       //比较哪条线段较短
                t=t1[l1+1]-nowt;
                P B=A+ (b[l2+1]-b[l2])*t/length(b[l2+1]-b[l2])- (a[l1+1]-a[l1])*t/length(a[l1+1]-a[l1]);
                ans = min(ans ,DistanceToSegment(P(0,0), A,B ));
                nowt=t1[++l1];
                A=B;//更新p点位置
            } else {
                t=t2[l2+1]-nowt;
                P B=A+ (b[l2+1]-b[l2])*t/length(b[l2+1]-b[l2])- (a[l1+1]-a[l1])*t/length(a[l1+1]-a[l1]);
                ans = min(ans ,DistanceToSegment(P(0,0), A,B ));
                nowt=t2[++l2];
                A=B;
            }
        }
        printf("%.12lf\n",(double)ans);
        return 0;
    }