Hatena::Grouptopcoder

kuuso1の日記

2015-03-15

SRM652 div2Hard NoRightTurnDiv2

| 09:53 | SRM652 div2Hard  NoRightTurnDiv2 - kuuso1の日記 を含むブックマーク はてなブックマーク - SRM652 div2Hard  NoRightTurnDiv2 - kuuso1の日記

http://community.topcoder.com/stat?c=problem_statement&pm=13644

  • XY平面上のN個の点の座標 x, y が与えられる
  • N点を順に訪れることを考える。この時、以下の条件を満たし全点を訪れる手順をみつけて答えよ
    • それまでに訪れたpathを横切らない
    • 右に曲がることはできない
  • そのような手順がない場合はヌルを返す

(制約)2 ≤ N ≤ 50, -1000 ≤ x[i],y[i] ≤ 1000 for all 0 ≤ i < N, 任意の3点は1直線に並ばない(collinear)

f:id:kuuso1:20150315090404p:image

(解法1)

pathを横切ることが出来ないことから、螺旋の外側に出られないことを考えると再外周をぐるっとまわる必要がある

・一周まわれば、次は内側に行くが、その後は内点の再外周をまた回る必要がある

・凸包の減少列を作って、うまくつないでいけばよさそう

f:id:kuuso1:20150315091005p:image

using System;
using System.Collections;
using System.Collections.Generic;

public class NoRightTurnDiv2 {
    public int[] findPath(int[] x, int[] y) {
        N=x.Length;
        Pair[] ALL=new Pair[N];
        //各座標のインデクスを覚えておく
        Dictionary<Pair,int> D=new Dictionary<Pair,int>();
        for(int i=0;i<N;i++){
            D.Add(new Pair(x[i],y[i]),i);
            ALL[i]=new Pair(x[i],y[i]);
        }
        
        //凸法の減少列に分解する
        List<List<Pair>> CHs=new List<List<Pair>>();
        bool[] used=new bool[N];
        while(true){
            List<Pair> L=new List<Pair>();
            for(int i=0;i<N;i++){
                if(!used[i])L.Add(ALL[i]);
            }
            if(L.Count==0)break;
            CHs.Add(CreateConvHull(L));
            foreach(var p in CHs[CHs.Count-1]){
                used[D[p]]=true;
            }
        }
    
        //外側から繋いでいく。各凸包内では時計回りに並んでいる
        List<int> ret=new List<int>();
        for(int i=0;i<CHs[0].Count;i++){
            ret.Add(D[CHs[0][i]]);
        }
        for(int j=1;j<CHs.Count;j++){
            int idx=-1;
            int fx=x[ret[ret.Count-1]]-x[ret[ret.Count-2]];
            int fy=y[ret[ret.Count-1]]-y[ret[ret.Count-2]];
            double theta=Math.PI+0.0001;
            for(int i=0;i<CHs[j].Count;i++){
                int tx=CHs[j][i].X-x[ret[ret.Count-1]];
                int ty=CHs[j][i].Y-y[ret[ret.Count-1]];
                double tt=Math.Acos((double)(fx*tx+fy*ty)/Math.Sqrt(fx*fx+fy*fy)/Math.Sqrt(tx*tx+ty*ty));
                if(tt<theta){
                    idx=i;
                    theta=tt;
                }
            }
            for(int i=0;i<CHs[j].Count;i++){
                int m=CHs[j].Count;
                ret.Add(D[CHs[j][(idx+i)%m]]);
            }
        }
        
        return ret.ToArray();
    }
    int N;
    struct Pair{
        public int X;
        public int Y;
        public Pair(int x,int y){
            X=x;Y=y;
        }
        public override String ToString(){
            return "("+X.ToString()+","+Y.ToString()+")";
        }
    }

    static List<Pair> CreateConvHull(List<Pair> L_){
        List<Pair> L=new List<Pair>(L_);
        L.Sort((x,y)=>x.X.CompareTo(y.X)==0?x.Y.CompareTo(y.Y):x.X.CompareTo(y.X));
        if(L.Count<=2)return L;
        
        List<Pair> ret=new List<Pair>();
        int k=0;
        //下半分
        for(int i=0;i<L.Count;i++){
            //末尾削除はO(1)なのでどんどん使う。
            k=ret.Count;
            while(k>1 && det((ret[k-1].X-ret[k-2].X),(ret[k-1].Y-ret[k-2].Y),(L[i].X-ret[k-1].X),(L[i].Y-ret[k-1].Y))<=0){
                ret.RemoveAt(k-1);
                k=ret.Count;
            }
            ret.Add(L[i]);
        }
        //上半分
        int t=ret.Count;
        for(int i=L.Count-2;i>=0;i--){
            //末尾削除はO(1)なのでどんどん使う。
            k=ret.Count;
            while(k>t && det((ret[k-1].X-ret[k-2].X),(ret[k-1].Y-ret[k-2].Y),(L[i].X-ret[k-1].X),(L[i].Y-ret[k-1].Y))<=0){
                ret.RemoveAt(k-1);
                k=ret.Count;
            }
            ret.Add(L[i]);
        }
        ret.RemoveAt(ret.Count-1);
        return ret;
    }
    static int det(int a,int b,int c,int d){
        return a*d-b*c;
    }
}

(解法2)

・凸包列を作ると最悪計算量がO(N^2 logN)と微妙に多いが、そもそもO(N)で走査できるならO(N^2)で行けるはずと言うところ。

f:id:kuuso1:20150315091627p:image

・あと走査について、内積と辺長からarccosで具体的に成す角を求めても良いが、今回のように最右であることだけなら以下のように2つのベクトルの向き(det)で判定したほうがよかった。

f:id:kuuso1:20150315094307p:image

using System;
using System.Collections;
using System.Collections.Generic;

public class NoRightTurnDiv2 {
    public int[] findPath(int[] x, int[] y) {
        
        int N=x.Length;
        Pair[] P=new Pair[N];
        for(int i=0;i<N;i++)P[i]=new Pair(x[i],y[i]);
        
        //左下の点を選ぶ
        int xmin=P[0].X;
        int ymin=P[0].Y;
        int strt=0;
        for(int i=0;i<N;i++){
            if(xmin>P[i].X || (xmin==P[i].X && ymin>P[i].Y)){
                strt=i;
                xmin=P[i].X;ymin=P[i].Y;
            }
        }
        //すでに選んだ点は除外して最右の点を選んでいく
        bool[] used=new bool[N];
        used[strt]=true;
        List<int> ret=new List<int>();
        ret.Add(strt);
        for(int i=1;i<N;i++){
            Pair Base=P[ret[ret.Count-1]];
            int trgt=-1;
            for(int j=0;j<N;j++){
                if(used[j])continue;
                if(trgt==-1){
                    trgt=j;
                    continue;
                }
                if(det(P[trgt]-Base,P[j]-Base)<0){
                    trgt=j;
                }
            }
            ret.Add(trgt);
            used[trgt]=true;
        }
        return ret.ToArray();
    }
    
    class Pair{
        public int X,Y;
        public Pair(int x,int y){
            X=x;Y=y;
        }
        public static Pair operator-(Pair p,Pair q){
            return new Pair(p.X-q.X,p.Y-q.Y);
        }
    }
    static int det(Pair p,Pair q){
        return p.X*q.Y-p.Y*q.X;
    }
}

コード量もスッキリして計算量もこちらの方がよい。

なんかでも凸包を延々つくるの、どこかでなんか応用が利きそう。

あと今回の日記で一番力が入っているのは、postscriptのwriter作って描いた凸包列の画。