Advertisement
YEZAELP

TOI14: plantation (Divide and Conquer)

Apr 7th, 2021 (edited)
179
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.75 KB | None
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4. using pii = pair <int, int>;
  5. using db = double;
  6. const db INF = (db) 2e9;
  7. vector <pii> point;
  8.  
  9. db distance(pii p1, pii p2){
  10.     db dx = p1.first - p2.first;
  11.     db dy = p1.second - p2.second;
  12.     return sqrt(dx*dx + dy*dy);
  13. }
  14.  
  15. db f(int l, int r){
  16.     db mn = INF;
  17.     for(int i=l;i<r;i++){
  18.         for(int j=i+1;j<=r;j++){
  19.             mn = min(mn, distance(point[i], point[j]));
  20.         }
  21.     }
  22.     return mn;
  23. }
  24.  
  25. db closest(int l, int r){
  26.     if(r-l+1 <= 3) return f(l, r);
  27.     int mid = (l+r)/2;
  28.     db d = min(closest(l, mid), closest(mid+1, r));
  29.     vector <pii> strip;
  30.     for(int i=l;i<=r;i++){
  31.         if(abs(point[mid].first - point[i].first) < d) strip.push_back({point[i].first, point[i].second});
  32.         // คิดเฉพาะช่วงแกน x ที่น้อยกว่า
  33.     }
  34.     sort(strip.begin(), strip.end());
  35.     int sz = strip.size();
  36.     db mn = INF;
  37.     for(int i=0;i<sz-1;i++){
  38.         for(int j=i+1;j<sz;j++){
  39.             if(strip[j].second - strip[i].second > d) break;
  40.             // ไม่สนใจที่ระยะแกน y มากกว่า
  41.             mn = min(mn, distance(strip[i], strip[j]));
  42.         }
  43.     }
  44.     return min(d, mn);
  45. }
  46.  
  47. int main(){
  48.  
  49.     int q;
  50.     scanf("%d", &q);
  51.  
  52.     while(q--){
  53.         int n;
  54.         db d, r;
  55.         scanf("%d%lf%lf", &n, &r, &d);
  56.         for(int i=1;i<=n;i++){
  57.             int x, y;
  58.             scanf("%d%d", &x, &y);
  59.             point.push_back({x, y});
  60.         }
  61.         sort(point.begin(), point.end());
  62.         db dist = closest(0, n-1);
  63.         if(dist - 2*r >= d) printf("Y");
  64.         else printf("N");
  65.         printf("\n");
  66.         point.clear();
  67.     }
  68.  
  69.     return 0;
  70. }
  71.  
Advertisement
RAW Paste Data Copied
Advertisement