mickypinata

TOI14: Plantation

Aug 1st, 2021 (edited)
152
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. typedef pair<int, int> pii;
  5.  
  6. const int N = 1e5;
  7.  
  8. pii coor[N + 1];
  9.  
  10. double dist(const pii &a, const pii &b){
  11.     int dx = a.first - b.first;
  12.     int dy = a.second - b.second;
  13.     return sqrt((double)dx * dx + (double)dy * dy);
  14. }
  15. bool sortByY(const pii &a, const pii &b){
  16.     if(a.second != b.second){
  17.         return a.second < b.second;
  18.     }
  19.     return a.first < b.first;
  20. }
  21.  
  22. double closestPair(int l, int r){
  23.     if(r - l <= 2){
  24.         double ClsP = 1e308;
  25.         for(int i = l; i <= r - 1; ++i){
  26.             for(int j = i + 1; j <= r; ++j){
  27.                 ClsP = min(ClsP, dist(coor[i], coor[j]));
  28.             }
  29.         }
  30.         return ClsP;
  31.     }
  32.     int m = (l + r) / 2;
  33.     double lClsP = closestPair(l, m);
  34.     double rClsP = closestPair(m + 1, r);
  35.     double ClsP = min(lClsP, rClsP);
  36.     vector<pii> cont;
  37.     for(int i = l; i <= r; ++i){
  38.         if(abs(coor[i].first - coor[m].first) < ClsP){
  39.             cont.push_back(coor[i]);
  40.         }
  41.     }
  42.     sort(cont.begin(), cont.end(), sortByY);
  43.     for(int i = 0; i < (int)cont.size() - 1; ++i){
  44.         for(int j = i + 1; j <= i + 7 && j < (int)cont.size(); ++j){
  45.             ClsP = min(ClsP, dist(cont[i], cont[j]));
  46.         }
  47.     }
  48.     return ClsP;
  49. }
  50.  
  51. int main(){
  52.  
  53.     int Q;
  54.     scanf("%d", &Q);
  55.     while(Q--){
  56.         int nTree, radius, tr;
  57.         scanf("%d%d%d", &nTree, &radius, &tr);
  58.         for(int i = 1; i <= nTree; ++i){
  59.             scanf("%d%d", &coor[i].first, &coor[i].second);
  60.         }
  61.         sort(coor + 1, coor + nTree + 1);
  62.         double ClsP = closestPair(1, nTree);
  63.         double reqDist = radius + radius + tr;
  64.         if(ClsP < reqDist){
  65.             cout << "N\n";
  66.         } else {
  67.             cout << "Y\n";
  68.         }
  69.     }
  70.  
  71.     return 0;
  72. }
  73.  
RAW Paste Data