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

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

1535： ◆adhRKFl5jU：2009/03/01(日) 18:46:46
jid39
問題番号 11
点数 100
-----
/*
TASK: Belt
LANG: C++
NAME: Kazuhiro Hosaka JPN13
*/
// O(N^3)
// AC?

#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; }

int N;
double D;
int X[1010],Y[1010];

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

int i,j,k;
int vx,vy,s,d;
int cnt1,cnt2,ans;

scanf("%i%lf", &N, &D);
for (i=0; i<N; ++i) {
scanf("%i%i", &X[i], &Y[i]);
}

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

D *= 2;
ans = 2;
for (i=0; i<N; ++i) for (j=i+1; j<N; ++j) {
cnt1 = cnt2 = 0;
vx = X[j] - X[i];
vy = Y[j] - Y[i];
d = (int)(D * sqrt(vx * vx + vy * vy));
for (k=0; k<N; ++k) {
s = vx * (Y[k] - Y[i]) - vy * (X[k] - X[i]);
if (0 <= s && s <= d) ++cnt1;
if (0 <= -s && -s <= d) ++cnt2;
}
ans = max(ans, cnt1);
ans = max(ans, cnt2);
}

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


return 0;
}
新着レスの表示

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

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

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

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