fork(1) download
copy 
  1. #include <iostream>
  2. #include <bits/stdc++.h>
  3. using namespace std;
  4. class node{
  5.     public:
  6.     int idx;
  7.     int x;
  8.     int y;
  9.     node(int xx=0,int yy=0,int ii=0){
  10.         idx=ii;
  11.         x=xx;
  12.         y=yy;
  13.     }
  14.     friend bool operator<(node a,node b);
  15. };
  16. bool operator<(node a,node b){
  17.     return(a.y<b.y);
  18. }
  19. bool cmp_fn(node a,node b){
  20.     return(a.x<b.x);
  21. }
  22. void solve(node pts[],int n){
  23.     int start,last;
  24.     int left =0;
  25.     double best=1000000000,v;
  26.     sort(pts,pts+n,cmp_fn);
  27.     set<node>box;
  28.     box.insert(pts[0]);
  29.     for(int i=1;i<n;i++){
  30.         while(left<i && pts[i].x-pts[left].x >best){
  31.             box.erase(pts[i]);
  32.             left++;
  33.         }
  34.         for(typeof(box.begin())it=box.begin();it!=box.end() && pts[i].y+best>=it->y;it++){
  35.             v=sqrt(pow(pts[i].y - it->y, 2.0)+pow(pts[i].x - it->x, 2.0));
  36.             if(v<best){
  37.                 best=v;
  38.                 start=it->idx;
  39.                 last=pts[i].idx;
  40.                 if(start>last)swap(start,last);
  41.             }
  42.         }
  43.         box.insert(pts[i]);
  44.     }
  45.     cout<<start<<" "<<last<<" "<<setprecision(6)<<fixed<<best;
  46. } 
  47. int main(){
  48.     int t,n,x,y;
  49.     cin>>n;
  50.     node pts[n];
  51.     for(int i=0;i<n;i++){
  52.         cin>>x>>y;
  53.         pts[i]=node(x,y,i);
  54.     }
  55.     solve(pts,n);
  56.     return 0;
  57. }
  58.  
  59.  
Success #stdin #stdout 0s 3476KB
comments ()
stdin
copy 
5
0 0
0 1
123 123
-123 123
-23 23
stdout
copy 
0 1 1.000000
https://ideone.com/Tzy5Au
problem CLOPPAIR, based on SPOJ submission 18602592 (C++14), 2017-01-19 11:36:21
language:
C++14 (gcc 8.3)
created:
8 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!