したらばTOP ■掲示板に戻る■ 全部 1-100 最新50 | メール | |

管理人の独り言（プログラミング関連）

1528： ◆adhRKFl5jU：2009/03/01(日) 18:35:40
jid30
問題番号 11
点数 100
-----
#include <stdio.h>
#include <math.h>
#include <vector>
#include <algorithm>
using namespace std;

main(){
int n;
int i,j;
double d;
double px[1000],py[1000];
int ans=0;
scanf("%d%lf",&n,&d);
for(i=0;i<n;i++){
scanf("%lf%lf",&px[i],&py[i]);
double qx=px[i]*cos(1)-py[i]*sin(1);
double qy=px[i]*sin(1)+py[i]*cos(1);
px[i]=qx;py[i]=qy;
}
d*=2;
if(n==1){printf("1\n");return 0;}
for(i=0;i<n;i++){
vector<pair<double,int> > event;
for(j=0;j<n;j++){
if(j==i)continue;
double theta=atan2(py[j]-py[i],px[j]-px[i]);
double l=hypot(py[j]-py[i],px[j]-px[i]);
event.push_back(make_pair(theta,-1));
event.push_back(make_pair(theta+M_PI,1));
if(l>d){
event.push_back(make_pair(theta-asin(d/l),1));
event.push_back(make_pair(theta+M_PI+asin(d/l),-1));
}
}
for(j=0;j<event.size();j++){
while(event[j].first<=0)event[j].first+=2*M_PI;
while(event[j].first>2*M_PI)event[j].first-=2*M_PI;
}
sort(event.begin(),event.end());
int cnt=0;
for(j=0;j<n;j++){
if(py[j]>=py[i] && py[j]<=py[i]+d)cnt++;
}
if(ans<cnt)ans=cnt;
for(j=0;j<event.size();j++){
cnt+=event[j].second;
if(ans<cnt)ans=cnt;
}
}
printf("%d\n",ans);
}
新着レスの表示

名前： E-mail（省略可）：

※書き込む際の注意事項はこちら

※画像アップローダーはこちら

（画像を表示できるのは「画像リンクのサムネイル表示」がオンの掲示板に限ります）
掲示板管理者へ連絡 無料レンタル掲示板