結果
問題 |
No.2923 Mayor's Job
|
ユーザー |
|
提出日時 | 2024-10-12 14:43:00 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 14 ms / 2,000 ms |
コード長 | 2,079 bytes |
コンパイル時間 | 2,320 ms |
コンパイル使用メモリ | 205,700 KB |
最終ジャッジ日時 | 2025-02-24 17:40:26 |
ジャッジサーバーID (参考情報) |
judge5 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 17 |
ソースコード
#include <bits/stdc++.h> using namespace std; template<typename T> struct Point{ public: T x,y; Point() : x(0),y(0) {} Point(T a,T b) : x(a),y(b) {} Point &operator=(const Point &b) = default; Point operator+(const Point &b){return Point(x+b.x,y+b.y);} Point operator-(const Point &b){return Point(x-b.x,y-b.y);} Point operator+=(const Point &b){return *this=*this+b;} Point operator-=(const Point &b){return *this=*this-b;} bool operator==(const Point &b){return x==b.x && y==b.y;} bool operator!=(const Point &b){return x!=b.x || y!=b.y;} bool operator<(const Point &b){ if(x == b.x) return y < b.y; else return x < b.x; } bool operator<=(const Point &b){return (*this) < b || (*this) == b;} bool operator>(const Point &b){return !((*this) <= b);} bool operator>=(const Point &b){return !((*this) < b);} friend T inner(const Point a,const Point b){return a.x*b.x+a.y*b.y;} friend T cross(const Point a,const Point b){return a.x*b.y-a.y*b.x;} friend T twodist(const Point a,const Point b){return (a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y);}//2乗で返す. }; template<typename T> istream &operator>>(istream &is,Point<T> &a){ is >> a.x >> a.y; return is; } template<typename T> ostream &operator<<(ostream &os,Point<T> &a){ os << a.x << " " << a.y; return os; } int main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); long long N,K; cin >> N >> K; vector<pair<int,int>> H(N); int idx = 0; for(auto &[h,p] : H) cin >> h,p = idx++; sort(H.begin(),H.end()); vector<Point<long long>> P(N); for(auto &p : P) cin >> p; vector<bool> del(N); for(int i=0; i<N; i++) for(int k=i+1; k<N; k++){ if(del.at(i) || del.at(k)) continue; auto [h,p1] = H.at(i); auto [h2,p2] = H.at(k); if(h == h2) continue; long long dist = twodist(P.at(p1),P.at(p2)); if(dist <= K*K) del.at(i) = true; } int answer = 0; for(auto d : del) if(!d) answer++; cout << answer << endl; }