fork(1) download
copy 
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. const int N = 1<<17;
  6. const long long INF = 2000000000000000007;
  7.  
  8. struct vp_node {
  9.     long long threshold;
  10.     pair < int, int > center;
  11.     vp_node *left, *right;
  12. };
  13.  
  14. typedef vp_node *node_ptr;
  15.  
  16. int tests,n;
  17. pair < int, int > pts[N],arr[N];
  18. long long ans;
  19. node_ptr root;
  20.  
  21. long long squared_distance(pair < int, int > a, pair < int, int > b) {
  22.     return (a.first-b.first)*1ll*(a.first-b.first) + (a.second-b.second)*1ll*(a.second-b.second);
  23. }
  24.  
  25. struct cmp_points {
  26.     pair < int, int > a;
  27.     cmp_points(){}
  28.     cmp_points(pair < int, int > p): a(p) {}
  29.     bool operator () (const pair < int, int > &x, const pair < int, int > &y) const {
  30.         return squared_distance(a,x)<squared_distance(a,y);
  31.     }
  32. };
  33.  
  34. void build(node_ptr &node, int a, int b) {
  35.     if(a>b) {
  36.         node=NULL;
  37.         return;
  38.     }
  39.     node=new vp_node();
  40.     if(a==b) {
  41.         node->threshold=0;
  42.         node->center=arr[a];
  43.         node->left=NULL;
  44.         node->right=NULL;
  45.         return;
  46.     }
  47.     int pos=a+rand()%(b-a+1);
  48.     swap(arr[a],arr[pos]);
  49.     node->center=arr[a];
  50.     sort(arr+a+1,arr+b+1,cmp_points(arr[a]));
  51.     node->threshold=squared_distance(arr[a],arr[(a+b)>>1]);
  52.     build(node->left,a,(a+b)>>1);
  53.     build(node->right,((a+b)>>1)+1,b);
  54. }
  55.  
  56. void query(node_ptr &node, pair < int, int > q, long long &ans) {
  57.     if(node==NULL) return;
  58.     if(node->center!=q) ans=min(ans,squared_distance(node->center,q));
  59.     if(node->left==NULL && node->right==NULL) {
  60.         return;
  61.     }
  62.     if(squared_distance(q,node->center)<=node->threshold) {
  63.         query(node->left,q,ans);
  64.         if(sqrt(squared_distance(node->center,q))+sqrt(ans)>sqrt(node->threshold)) 
  65.             query(node->right,q,ans);
  66.     }
  67.     else {
  68.         query(node->right,q,ans);
  69.         if(sqrt(squared_distance(node->center,q))-sqrt(ans)<sqrt(node->threshold)) 
  70.             query(node->left,q,ans);
  71.     }
  72. }
  73.  
  74. int main() {
  75.     int i;
  76.  
  77.     scanf("%d", &tests);
  78.     while(tests--) {
  79.         scanf("%d", &n);
  80.         for(i=1;i<=n;i++) {
  81.             scanf("%d %d", &arr[i].first, &arr[i].second);
  82.             pts[i]=arr[i];
  83.         }
  84.  
  85.         build(root,1,n);
  86.  
  87.         for(i=1;i<=n;i++) {
  88.             ans=INF;
  89.             query(root,pts[i],ans);
  90.             printf("%lld\n", ans);
  91.         }
  92.     }
  93.  
  94.     return 0;
  95. }
  96.  
Success #stdin #stdout 0s 17288KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/o1wTNS
language:
C++14 (gcc 8.3)
created:
6 years ago
visibility:
public

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!