敗戦記

PKU 2398 Toy Storage

PKU

http://poj.org/problem?id=2398

不揃いな仕切りがある箱のある座標に物を入れて、何個入ってる空間が何個あるかを答えろというような問題。

あまり必要なさそうだけれど、入れるときに二分探索しました。

int in[1001];
PI ca[1002];

main(){
  int n,m,x1,y1,x2,y2;
  while(cin>>n,n){
    memset(in,0,sizeof(in));
    cin>>m>>x1>>y1>>x2>>y2;
    ca[0]=mp(x1,x1);
    rep(i,n)cin>>ca[i+1].F>>ca[i+1].S;
    ca[1+n]=mp(x2,x2);
    sort(ca,ca+n+1);
    rep(i,m){
      int xi,yi;
      cin>>xi>>yi;
      int l=0,u=n+1;
      while(l+1<u){
        int med=(l+u)/2;
        double xm=1.0*(ca[med].F-ca[med].S)/(y1-y2)*(yi-y1)+ca[med].F;
        if(xm>xi)u=med;
        else l=med;
      }
      in[l]++;
    }
    map<int,int> app;
    rep(i,n+1)if(in[i])++app[in[i]];
    cout<<"Box"<<endl;
    FOR(it,app)cout<<it->F<<": "<<it->S<<endl;
  }
}

Permalink | コメント(0) | トラックバック(1) | 08:34