Hatena::Grouptopcoder

kuuso1の日記

2017-06-24

AtCoder Regular Contest 076 E - Connected?

| 02:25 | AtCoder Regular Contest 076 E - Connected? - kuuso1の日記 を含むブックマーク はてなブックマーク - AtCoder Regular Contest 076 E - Connected? - kuuso1の日記

http://arc076.contest.atcoder.jp/tasks/arc076_c

  • R×C の長方形の盤面に、1 から N までの整数が 2 つずつ書かれている.それぞれの座標は(Xi1,Yi1),(Xi2,Yi2)で互いに異なる
  • それぞれの数字同士を曲線で結ぶとき,どの曲線も交差しないように,盤面内で結ぶことができるかを判定する

(制約)1 ≤ N ≤ 100000,1 ≤ R,C ≤ 10^8, (Xi1,Yi1),(Xi2,Yi2) ∈ [0,R] × [0,C] for all i

・絵をかいて考察すると,交差を避けられないのは端点が両方とも盤面の壁に存在するもの同士に限られることが分かる.

 (曲線によって盤面が分断されると考えると,異なる連結成分に端点が分断されてしまう曲線があるとダメ)

・両端が盤面の壁に存在するものばかりを集めてきて交差判定するのだけど,O(N^2)だと間に合わない.

・各壁に着目して,ある壁にそってソートすると残りの端点が交差しない,みたいなやつでできる気もしたが実装無理過ぎてギブアップ.

・(コンテスト後)一次元に直してスタックという情報を見る.なるほど.

f:id:kuuso1:20170625021958p:image

・実装も軽い.

class Sol{
    public void Solve(){
        
        List<Pair> L = new List<Pair>();
        for(int i=0;i<N;i++){
            if(IsOnTheKabe(P[i][0],P[i][1]) && IsOnTheKabe(P[i][2],P[i][3])){
                long f = Enc(P[i][0],P[i][1]);
                long t = Enc(P[i][2],P[i][3]);
                if(f > t){ var tmp = t; t = f; f = tmp; }
                L.Add(new Pair(f,t));
            }
        }
        
        L.Sort((p,q) => p.Fr.CompareTo(q.Fr));
        
        Stack<Pair> Stk = new Stack<Pair>();
        foreach(var p in L){
            while(Stk.Count > 0){
                var enclosure = Stk.Peek();
                if(p.Fr > enclosure.To){
                    Stk.Pop();
                    continue;
                } 
                if(p.Fr > enclosure.Fr && p.To < enclosure.To){
                    break;
                } 
                Console.WriteLine("NO");
                return;
            }
            Stk.Push(p);
        }
        Console.WriteLine("YES");
    }
    
    class Pair{
        public long Fr,To;
        public Pair(long f, long t){
            Fr = f; To = t;
        }
    }
    
    bool IsOnTheKabe(long x, long y){
        return (x == 0 || x == R) || (y == 0 || y == C);
    }
    long Enc(long x, long y){
        // (0,0) -> (R,0) -> (R,C) -> (0,C) -> (0,0)
        if(y == 0) return x;
        if(x == R) return R + y;
        if(y == C) return R + C + (R - x);
        if(x == 0) return R + C + R + (C - y);
        return 0;
    }
    
    long R, C;
    int N;
    long[][] P;
    public Sol(){
        var d = rla();
        R = d[0]; C = d[1]; N = (int)d[2];
        P = new long[N][];
        for(int i=0;i<N;i++) P[i] = rla();
    }

    static long[] rla(char sep=' '){return Array.ConvertAll(Console.ReadLine().Split(sep),e=>long.Parse(e));}
}

・日記書いたの久しぶりと思ったら前回もDEGwerさん回だった.