PKU 2398 Toy Storage
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; } }