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

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

1534： ◆adhRKFl5jU：2009/03/01(日) 18:45:30
jid38
問題番号 11
点数 100
-----
/*
TASK: Belt
LANG: C++
NAME: Kazuhiro Hosaka JPN13
*/

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <cassert>
#include <iostream>
#include <sstream>
#include <string>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include <utility>
#include <algorithm>
#include <bitset>
#include <complex>

using namespace std;

typedef long long Int;
typedef vector<int> vint;
typedef pair<int,int> pint;
#define mp make_pair

template<class T> void pv(T a, T b) { for (T i=a; i!=b; ++i) cout << *i << " "; cout << endl; }
template<class T> void pvp(T a, T b) { for (T i=a; i!=b; ++i) cout << "(" << i->first << ", " << i->second << ") "; cout << endl; }

const double PI = acos(-1.0);

int N;
double D;
double X[1010],Y[1010];
pair<double,int> ev[4010];
int len;

double mod(double a, double m) {
return fmod(fmod(a, m) + m, m);
}

int main() {
//freopen("belt.in", "r", stdin);

int i,j;
int xx,yy;
double x,y,r,t,s;
int ans,tmp;

scanf("%i%lf", &N, &D);
for (i=0; i<N; ++i) {
scanf("%i%i", &xx, &yy);
X[i] = xx * cos(1.0) - yy * sin(1.0);
Y[i] = xx * sin(1.0) + yy * cos(1.0);
}

if (N <= 2) {
printf("%i\n", N);
return 0;
}

D *= 2;
ans = 2;
for (i=0; i<N; ++i) {
tmp = 1;
len = 0;
for (j=0; j<N; ++j) if (j != i) {
x = X[j] - X[i];
y = Y[j] - Y[i];
r = sqrt(x * x + y * y);
t = atan2(y, x);
if (0 <= -y && -y <= D) ++tmp;
if (r <= D) {
ev[len++] = mp(mod(t, PI*2), 1);
ev[len++] = mp(mod(t + PI, PI*2), -1);
} else {
s = asin(D / r);
ev[len++] = mp(mod(t, PI*2), 1);
ev[len++] = mp(mod(t + s, PI*2), -1);
ev[len++] = mp(mod(t + PI - s, PI*2), 1);
ev[len++] = mp(mod(t + PI, PI*2), -1);
}
}
sort(ev, ev+len);
for (j=0; j<len; ++j) {
ans = max(ans, tmp += ev[j].second);
}
}

printf("%i\n", ans);


return 0;
}
新着レスの表示

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

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

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

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