fork(1) download
copy 
  1.  
  2. /*
  3. dfs-kefa and park;
  4. bfs-1174
  5. mergesort with indexing kefaB
  6. merge sort-annya and ghost
  7. qsort-building permutation
  8. bfs using vector and queue - the two routes
  9. power function- om nom and perk
  10. dfs in tree- om nom and perk
  11. */
  12. #include <stdio.h>
  13. #include <cstdio>
  14. #include <cstring>
  15. #include <cstdlib>
  16. #include<climits>
  17. #include <iostream>
  18. #include <cmath>
  19. #include <algorithm>
  20. #include <list>
  21. #include <stack>
  22. #include<queue>
  23. #include<vector>
  24. #include <utility>
  25. #include <ctime>
  26. #include <string>
  27. #include <map>
  28.  
  29. #define ll long long
  30. #define SIZE 1000
  31. #define max3(a, b, c) max(a, b) > max(b, c) ? max(a, b) : max(b, c)
  32. #define min3(a, b, c) min(a, b) < min(b, c) ? min(a, b) : min(b, c)
  33. #define mi(a,b) (a>b)? b : a
  34. #define digit(c) (c - '0')
  35.  
  36. using namespace std;
  37. ll a[2010],b[2010];
  38. void merge(ll, ll , ll );
  39. void mergesort(ll low, ll high)
  40. {
  41.     ll mid;
  42.     if (low < high)
  43.     {
  44.         mid=(low+high)/2;
  45.         mergesort(low,mid);
  46.         mergesort(mid+1,high);
  47.         merge(low,high,mid);
  48.     }
  49.     return;
  50. }
  51. void merge(ll low, ll high, ll mid)
  52. {
  53.     ll i, j, k, c[2010],d[2010];
  54.     i = low;
  55.     k = low;
  56.     j = mid + 1;
  57.     while (i <= mid && j <= high)
  58.     {
  59.         if (a[i] < a[j])
  60.         {
  61.             c[k] = a[i];
  62.             d[k]=b[i];
  63.             k++;
  64.             i++;
  65.         }
  66.         else
  67.         {
  68.             c[k] = a[j];
  69.             d[k]=b[j];
  70.             k++;
  71.             j++;
  72.         }
  73.     }
  74.     while (i <= mid)
  75.     {
  76.         c[k] = a[i];
  77.         d[k]=b[i];
  78.         k++;
  79.         i++;
  80.     }
  81.     while (j <= high)
  82.     {
  83.         c[k] = a[j];
  84.         d[k]=b[j];
  85.         k++;
  86.         j++;
  87.     }
  88.     for (i = low; i < k; i++)
  89.     {
  90.         a[i] = c[i];
  91.         b[i] = d[i];
  92.     }
  93. }
  94.  
  95. int main()
  96. {
  97.     ll n,p,q,r,s,i,x,y,m1=0,m2=0,ans=0,pre=0;
  98.     ll l[2010],m[2010],t[2010],k[2010];
  99.     cin>>n>>p>>q>>r>>s;
  100.     for(i=0;i<n;i++){
  101.         cin>>x>>y;
  102.         m[i]=(p-x)*(p-x)+(q-y)*(q-y);
  103.         t[i]=(r-x)*(r-x)+(s-y)*(s-y);
  104.         //cout<<a[i]<<" "<<b[i]<<endl;
  105.     }
  106.     for(i=0;i<n;i++){
  107.         a[i]=m[i];
  108.         b[i]=t[i];
  109.         //cout<<a[i]<<" "<<b[i]<<endl;
  110.     }
  111.     mergesort(0,n-1);
  112.     //for(i=0;i<n;i++)cout<<a[i]<<" "<<b[i]<<endl;
  113.  
  114.     l[n-1]=0;
  115.     m1=b[n-1];
  116.     pre=b[n-1];
  117.     for(i=n-2;i>=0;i--){
  118.         if(b[i+1]>m1)m1=b[i+1];
  119.         else if(b[i+1]>pre && a[i]!=a[i+1])pre=b[i+1];
  120.         if(a[i]!=a[i+1]){
  121.             l[i]=m1;
  122.         }
  123.         else if(a[i]==a[i-1]){
  124.             l[i]=pre;
  125.         }
  126.     }
  127.     m2=a[n-1];
  128.     for(i=n-2;i>=0;i--){
  129.         if(a[i]+l[i]<m2)m2=a[i]+l[i];
  130.     }
  131.  
  132.     //cout<<m2;
  133.  
  134.     for(i=0;i<n;i++){
  135.         b[i]=m[i];
  136.         a[i]=t[i];
  137.         //cout<<a[i]<<" "<<b[i]<<endl;
  138.     }
  139.     mergesort(0,n-1);
  140.     //for(i=0;i<n;i++)cout<<a[i]<<" "<<b[i]<<endl;
  141.     l[n-1]=0;
  142.     m1=b[n-1];
  143.     pre=b[n-1];
  144.     for(i=n-2;i>=0;i--){
  145.         if(b[i+1]>m1)m1=b[i+1];
  146.         else if(b[i+1]>pre && a[i]!=a[i+1])pre=b[i+1];
  147.         if(a[i]!=a[i+1]){
  148.             l[i]=m1;
  149.         }
  150.         else if(a[i]==a[i-1]){
  151.             l[i]=pre;
  152.         }
  153.     }
  154.     ll m3=a[n-1];
  155.     for(i=n-2;i>=0;i--){
  156.         if(a[i]+l[i]<m3)m3=a[i]+l[i];
  157.     }
  158.     cout<<min(m2,m3);
  159.     return 0;
  160. }
  161.  
  162.  
Success #stdin #stdout 0s 3452KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/8Udk05
language:
C++ (gcc 8.3)
created:
8 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!