結果
問題 | No.202 1円玉投げ |
ユーザー |
![]() |
提出日時 | 2016-08-08 22:01:35 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 483 ms / 5,000 ms |
コード長 | 1,595 bytes |
コンパイル時間 | 1,358 ms |
コンパイル使用メモリ | 111,216 KB |
実行使用メモリ | 10,368 KB |
最終ジャッジ日時 | 2024-12-22 10:27:13 |
合計ジャッジ時間 | 8,109 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 38 |
ソースコード
#include <iostream>#include <sstream>#include <string>#include <vector>#include <functional>#include <tuple>#include <climits>#include <algorithm>#include <queue>#include <unordered_map>#include <unordered_set>#include <set>#include <numeric>#include <map>#include <cmath>#include <cstdlib>#include <iomanip>using namespace std;int main(){int N;cin >> N;vector<int> X(N), Y(N);for(int i=0; i<N; i++)cin >> X[i] >> Y[i];constexpr int max_x = 20000;constexpr int max_y = 20000;constexpr int bucket_size = 10;using bucket_t = tuple<int, int>;enum {x = 0,y = 1};map<tuple<int, int>, bucket_t> bucket;int count = 0;for(int i=0; i<N; i++) {bucket_t b = make_tuple(X[i], Y[i]);tuple<int, int> bp = make_tuple(X[i]/bucket_size, Y[i]/bucket_size);if(bucket.find(bp) != bucket.end()) continue;for(int ix=-2; ix<=2; ix++) {for(int iy=-2; iy<=2; iy++) {tuple<int, int> neighbor = bp;get<x>(neighbor) = get<x>(neighbor) + ix;get<y>(neighbor) = get<y>(neighbor) + iy;if(bucket.find(neighbor) != bucket.end()) {const int squared_distance = pow(get<x>(bucket[neighbor])-get<x>(b), 2) + pow(get<y>(bucket[neighbor])-get<y>(b), 2);if(squared_distance < 400)goto next;}}}bucket[bp] = make_tuple(X[i], Y[i]);count++;next:;}cout << count << endl;}