土下座しながら探索中

主に競技プログラミング

LiveArchive 5873 : Tree Inspections

問題リンク : https://icpcarchive.ecs.baylor.edu/external/58/5873.pdf

問題概要 :
2次元平面上にT本の木とH本の道が存在する.
T本の木のうち60%以上を道の上から見ることはできるだろうか?
木は以下の条件を満たすとき、道から見ることができる :
道から垂直に木まで線を引いた際に、その間に他の木が立っていない.

例えば、Sample Input は次のようになる.
黒い点が木を、赤い線が道を表す.
f:id:tei3344:20161031011235p:plain
f:id:tei3344:20161031011305p:plain
f:id:tei3344:20161031011325p:plain

制約 :
1 <= T,P <= 10^5

解法 :
各木について、その木が道から見ることができるかどうかを確かめる
ただし愚直に実装すると T * P ( = 10^10 ) となり間に合わない
そこで、ある木が見えるかどうかを判定する際には、その木に最も近い上下左右の木のみを用いる

つまり、その木に最も近い上下左右の木を求め、その木と最も近い上下左右の木のいずれかとの間に道が存在するかどうかを判定する
これなら全体でもT * 4 * logPとなり間に合う

例えば、以下のようなケースについて考える
f:id:tei3344:20161031012227p:plain
赤い点が今見えるかどうかを判定したい木とする
このとき、この木が見えるかどうかの判定に必要な木は青い点として表されている以下の3本である
f:id:tei3344:20161031012422p:plain
これらの青い点はlower_boundで求めることができる
f:id:tei3344:20161031013257p:plain
f:id:tei3344:20161031013554p:plain
あとはその木とlower_boundで求めた木の間に道があるかどうかをlower_boundで求める

コード :

#include<bits/stdc++.h>

#define REP(i,s,n) for(int i=s;i<n;++i)
#define rep(i,n) REP(i,0,n)
#define EPS (1e-8)
#define equals(a,b) (fabs((a)-(b))<EPS)

using namespace std;

bool LTE(double a,double b) { return equals(a,b) || a < b; }

const int IINF = INT_MAX;

struct Data {
  int x,y;
};

int dx[] = {0,1,0,-1}; // ↓→↑←
int dy[] = {1,0,-1,0};

int T, P;

bool cmp_x(const Data &v1, const Data &v2) {
  if( v1.x != v2.x ) return v1.x < v2.x;
  return v1.y < v2.y;
}

bool cmp_y(const Data &v1, const Data &v2) {
  if( v1.y != v2.y ) return v1.y < v2.y;
  return v1.x < v2.x;
}

#define ALL(x) x.begin(),x.end()

void compute(vector<Data> &vec, vector<int> &hs, vector<int> &vs) {
  vector<Data> adj[4];
  vector<Data> xs,ys;
  rep(i,T) xs.push_back(vec[i]), ys.push_back(vec[i]);
  sort(ALL(xs),cmp_x);
  sort(ALL(ys),cmp_y);
  sort(ALL(hs));
  sort(ALL(vs));

  rep(i,T) {
    // ↓ xは同じ y+
    int ptr = lower_bound(ALL(xs),vec[i],cmp_x) - xs.begin();
    ++ptr;
    if( ptr < T && xs[ptr-1].x == xs[ptr].x ) {
      adj[0].push_back(xs[ptr]);
    } else {
      adj[0].push_back((Data){vec[i].x,IINF});
    }
    
    // → yは同じ x+
    ptr = lower_bound(ALL(ys),vec[i],cmp_y) - ys.begin();
    ++ptr;
    if( ptr < T && ys[ptr-1].y == ys[ptr].y ) {
      adj[1].push_back(ys[ptr]);
    } else {
      adj[1].push_back((Data){IINF,vec[i].y});
    }


    // ↑ xは同じ y-
    ptr = lower_bound(ALL(xs),vec[i],cmp_x) - xs.begin();
    --ptr;
    if( ptr >= 0 && xs[ptr+1].x == xs[ptr].x ) {
      adj[2].push_back(xs[ptr]);
    } else {
      adj[2].push_back((Data){vec[i].x,-IINF});
    }

    // ← yは同じ x-
    ptr = lower_bound(ALL(ys),vec[i],cmp_y) - ys.begin();
    --ptr;
    if( ptr >= 0 && ys[ptr+1].y == ys[ptr].y ) {
      adj[3].push_back(ys[ptr]);
    } else {
      adj[3].push_back((Data){-IINF,vec[i].y});
    }
  }

  vector<bool> ok(T,false);
  rep(i,T) {
    bool see = false;
    rep(j,4) {
      Data point = adj[j][i];
      if( point.x == vec[i].x ) {
	int pos = lower_bound(ALL(hs),min(vec[i].y,point.y)) - hs.begin();

	if( pos >= (int)hs.size() ) continue;
	if( min(point.y,vec[i].y) <= hs[pos] && hs[pos] <= max(point.y,vec[i].y) ) {
	  see = true;
	  break;
	}
      } else {
      	int pos = lower_bound(ALL(vs),min(vec[i].x,point.x)) - vs.begin();
	if( pos >= (int)vs.size() ) continue;
	if( min(point.x,vec[i].x) <= vs[pos] && vs[pos] <= max(point.x,vec[i].x) ) {
	  see = true;
	  break;
	}
      }
    }
    if( see ) ok[i] = true;
  }
  double cnt = 0;
  rep(i,T) cnt += ok[i];
  if( LTE(0.6,cnt/(double)T) ) {
    puts("PASSED");
  } else {
    puts("FAILED");
  }
}

int main() {
  int F;
  while( cin >> F ) {
    rep(_,F) {
      cin >> T >> P;
      vector<Data> vec(T);
      vector<int> hs,vs;
      rep(i,T) cin >> vec[i].x >> vec[i].y;
      rep(i,P) {
	char c;
	int v;
	cin >> c >> v;
	if( c == 'H' ) hs.push_back(v);
	else           vs.push_back(v);
      }
      compute(vec,hs,vs);
    }
  }
  return 0;
}