AOJ 2201: 不死の宝石

Problem

嘘解法で通しました。

Source

Algorithm

  • 直線の傾きを変えながらひたすら試す。
  • まず、直線の傾きが固定されている場合の最適解は次のようにして求まる。
    • その傾きの直線を適当にひとつ描き、各宝石の中心の点との距離を求める。
      • ここで、直線は全て宝石の中心点よりも 右 or 左 側にくるようにする。
      • あるいは、直線の左側にあるような点は、距離に -1 を掛ける。
    • ある宝石の半径を r, 磁力の強さを m, 中心点と直線の距離を d とすると、その直線を
      • d-r-m 以上 d-r 以下、または d+r 以上 d+r+m 以下
    • だけずらしたときに限ってその宝石が回収される。
    • それぞれの宝石について、{d-r-m, IN}, {d-r, OUT}, {d+r, IN}, {d+r+m, OUT} の4つのイベントを列挙する。
    • これらのイベントを距離でソートして下から見ていき、INならカウンタを ++, OUTならカウンタを -- とやっていって、その間の最大値が答え。
  • 次に、直線の傾きについて考える。
    • 基本的に、さっきのエントリに書いた通り。再掲します。
      • 傾きの区間 [a, b] における最適解を求めるには、a のイベント列と b のイベント列を求める。
        • それらが同じであれば、それ以上細かくする必要がないので、適当にひとつ傾きを決めてそのときの最適解を返す。
        • 違うのであれば、[a, (a+b)/2] の最適解と [(a+b)/2, b] の最適解を求めて大きい方を返す。
    • 微妙に違うところとして、イベント列を直接比べる代わりにハッシュを求める。
    • また、誤差のせいで a, b が限りなく近くなってもイベント列が異なったままのことがあるので、適当なところで打ち切る。
      • ちょっとここ汚い。
      • 区間の長さが 1.0e-11 未満になったら打ち切りとしましたが、これも解答データとdiffをとりつつ見つけた値です。1.0e-10だとダメ。
      • まだまだ撃墜ケースがありそうな気がします。

Code

  • ジャッジデータの E1 と E2 に通ることを確認しました。
    • それぞれ3分以下で出てきました。
  • AOJではもちろんTLE.
  • 誤差のあたりを上手くやれたらそれなりに速くなると思うんだけど。
#include <iostream>
#include <sstream>
#include <queue>
#include <map>
#include <set>
#include <vector>
#include <numeric>
#include <algorithm>
#include <string>

#include <cassert>
#include <cstdlib>
#include <cmath>
#include <cstdio>
#include <cstring>

#define REP(i,e) for(int i=0;i<(int)(e);i++)
#define FOR(i,b,e) for(int i=(int)(b);i<(int)(e);i++)
#define ALL(c) (c).begin(), (c).end()

using namespace std;

#include <complex>
#include <vector>

using namespace std;

// constants
const double eps=1e-9;
const double inf=1e256;
const double pi=acos(-1);

// type definition
typedef complex<double> pt;
struct seg{ pt s,d; };
typedef seg line;


inline bool eq(double a,double b){ return fabs(a-b)<eps; }
inline bool pteq(pt a,pt b){ return eq(real(a),real(b)) && eq(imag(a),imag(b));}

inline double dot  (pt a,pt b){ return real(conj(a)*b); }
inline double cross(pt a,pt b){ return imag(conj(a)*b); }

// counterclockwise
//                 +1
// +2 --- (l.s) ----0---> (l.d) --- -2
//                 -1            (Same as Mr. Maebara's)
inline int ccw(line l,pt p){
  p-=l.s;
  double c=cross(l.d-l.s,p);
  if(!eq(c,0)) return (c<0 ? -1 : 1);
  if(dot(l.d-l.s,p)<-eps) return 2;
  if(norm(l.d-l.s)+eps<norm(p)) return -2;
  return 0;
}

inline double distLP1(const line& l,const pt &p){
  return fabs(cross(l.d-l.s,p-l.s));
}

struct C{ pt o; double r,m; };
typedef vector<C> vc;

struct E{ double p; int c; bool in; };

inline bool cmp(const E& a, const E& b){ 
  if(eq(a.p,b.p)) return a.in>b.in;
  return a.p<b.p;
}

const int H=1000000007;


int calc(vc &v,double t,int &h){
  line l={pt(0,0),pt(1,0)*polar(1.0,t)};

  static E e[1000];
  int cnt=0;

  REP(i,v.size()){
    double d=distLP1(l,v[i].o);
    int cc=ccw(l,v[i].o);
    if(abs(cc)==1) d*=cc;
    else           d=0.0;
    
    double r=v[i].r, m=v[i].m;
    e[cnt++]=(E){d-r-m,i,true};
    e[cnt++]=(E){d-r  ,i,false};
    e[cnt++]=(E){d+r  ,i,true};
    e[cnt++]=(E){d+r+m,i,false};
  }

  stable_sort(e,e+cnt,cmp);
  int ans=0, a=0;
  REP(i,cnt){
    e[i].in ? ++a : --a;
    ans=max(ans,a);
  }

  h=0;
  REP(i,cnt){ h*=H;h+=e[i].in;h*=H;h+=e[i].c; }
  return ans;
}

int compute(vc &v,double src,double dst,int sh,int dh){
  int c,ch; c=calc(v,(src+dst)/2,ch);
  
  if(dst-src<1e-11) return c;
  
  int a=0,b=0;
  if(sh!=ch) a=compute(v,src,(src+dst)/2,sh,ch);
  if(dh!=ch) b=compute(v,(src+dst)/2,dst,ch,dh);

  return max(max(a,b),c);
}

int main(){
  int n;
  while(cin >> n && n){
    vc v(n);
    REP(i,n) cin >> v[i].o.real() >> v[i].o.imag() >> v[i].r >> v[i].m;
    int a,ah,b,bh;
    a=calc(v,-pi/2,ah); b=calc(v,pi/2,bh);
    int ans=compute(v,-pi/2,pi/2,ah,bh);
    cout << ans << endl;
  }  
}