fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. const int N = 1e5 + 5;
  5.  
  6. struct Point {
  7.     int val[2];
  8.  
  9.     Point() {}
  10.  
  11.     void scan(int d = 2) {
  12.         for(int i = 0 ; i < d ; i++) {
  13.             int x;
  14.             scanf("%d", &x);
  15.             val[i] = x;
  16.         }
  17.     }
  18.  
  19.     int operator *(Point other) const {
  20.         int ret = 0;
  21.         for(int i = 0 ; i < 2 ; i++) {
  22.             ret += val[i] * other.val[i];
  23.         }
  24.         return ret;
  25.     }
  26.  
  27.     long long get_dist(Point other) {
  28.         long long ret = 0;
  29.         for(int i = 0 ; i < 2 ; i++) {
  30.             ret += 1ll * (val[i] - other.val[i]) * (val[i] - other.val[i]);
  31.         }
  32.         return ret;
  33.     }
  34. };
  35.  
  36. struct KDTree {
  37.     vector<Point> points;
  38.     int dim;
  39.  
  40.     KDTree(int _d = 1) {
  41.         dim = _d;
  42.         points.clear();
  43.     }
  44.  
  45.     int get_size() {
  46.         return points.size();
  47.     }
  48.  
  49.     void add(vector<Point> v) {
  50.         for(Point x : v) {
  51.             points.push_back(x);
  52.         }
  53.     }
  54.  
  55.     void build() {
  56.         build(0, 0, points.size());
  57.     }
  58.  
  59.     void build(int depth, int l, int r) {
  60.         if(l >= r) {
  61.             return;
  62.         }
  63.  
  64.         int modd = depth % dim;
  65.         int mid = (l + r) / 2;
  66.         nth_element(points.begin() + l, points.begin() + mid, points.begin() + r, [&](Point a, Point b) {
  67.             return a.val[modd] < b.val[modd];
  68.         });
  69.  
  70.         build(depth + 1, l, mid);
  71.         build(depth + 1, mid+1, r);
  72.     }
  73.  
  74.     void query(int depth, int l, int r, Point tgt, long long &best) {
  75.         if(l >= r) {
  76.             return;
  77.         }
  78.  
  79.         int modd = depth % dim;
  80.         int mid = (l + r) / 2;
  81.         long long cur = tgt.get_dist(points[mid]);
  82.  
  83.         if(cur > 0)
  84.             best = min(best, cur);
  85.  
  86.         int l1 = l;
  87.         int r1 = mid;
  88.         int l2 = mid+1;
  89.         int r2 = r;
  90.  
  91.         if(tgt.val[modd] > points[mid].val[modd]) {
  92.             swap(l1, l2);
  93.             swap(r1, r2);
  94.         }
  95.  
  96.         query(depth+1, l1, r1, tgt, best);
  97.  
  98.         int delta = tgt.val[modd] - points[mid].val[modd];
  99.         long long delta2 = 1ll * delta * delta;
  100.  
  101.         if(delta2 < best) {
  102.             query(depth+1, l2, r2, tgt, best);
  103.         }
  104.     }
  105.  
  106.     long long query(Point tgt) {
  107.         long long ret = 4e18;
  108.  
  109.         query(0, 0, points.size(), tgt, ret);
  110.  
  111.         return ret;
  112.     }
  113. };
  114.  
  115. KDTree tree;
  116. int n;
  117. vector<Point> arr;
  118.  
  119. void read() {
  120.     scanf("%d", &n);
  121.     arr.clear();
  122.     arr.resize(n);
  123.     for(int i = 0 ; i < n ; i++) {
  124.         arr[i].scan(2);
  125.     }
  126. }
  127.  
  128. void init() {
  129.     tree = KDTree(2);
  130.     tree.add(arr);
  131.     tree.build();
  132. }
  133.  
  134. long long query(Point p) {
  135.     return tree.query(p);
  136. }
  137.  
  138. void work() {
  139.     for(int i = 0 ; i < n ; i++) {
  140.         printf("%lld\n", query(arr[i]));
  141.     }
  142. }
  143.  
  144. int main() {
  145.     int t;
  146.     scanf("%d", &t);
  147.  
  148.     for(int tc = 1 ; tc <= t ; tc++) {
  149.         read();
  150.         init();
  151.         work();
  152.     }
  153.     return 0;
  154. }
Success #stdin #stdout 0s 15248KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/lRjQJ3
language:
C++ (gcc 8.3)
created:
6 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!