Advertisement
Guest User

Untitled

a guest
Jul 27th, 2017
64
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 3.91 KB | None | 0 0
  1.  
  2. #include <bits/stdc++.h>
  3. #define MAX 1010
  4. #define f1 100000ll
  5. #define f2 10000000000ll
  6. #define f3 1000000000000000ll
  7.  
  8. typedef long long ll;
  9. using namespace std;
  10.  
  11. struct Node
  12. {
  13.     int index;
  14.     ll value;
  15.     Node(){}
  16.     Node(int index, ll value) : index(index), value(value) {}
  17.     bool operator < ( const Node &o ) const
  18.     {
  19.         return value < o.value;
  20.     }
  21. };
  22.  
  23. ll xs[MAX];
  24. ll ys[MAX];
  25. vector<vector<Node>> values(MAX, vector<Node>(MAX));
  26. ll dist[MAX][MAX];
  27.  
  28. int main()
  29. {
  30.     std::ios::sync_with_stdio(0);
  31.     cin.tie(0);
  32.     freopen("input.txt", "r", stdin);
  33.     freopen("output.txt", "w", stdout);
  34.     int n;
  35.     while(cin>>n)
  36.     {
  37.  
  38.     for( int i = 0; i < n; i++ )
  39.     {
  40.             cin>>xs[i]>>ys[i];
  41.     }
  42.     ll dx, dy;
  43.     for( int i = 0; i < n; i++ )
  44.     {
  45.         for( int j = 0; j < n; j++)
  46.         {
  47.             dx = xs[i] - xs[j];
  48.             dy = ys[i] - ys[j];
  49.             dist[i][j] = dx*dx + dy*dy;
  50.             values[i][j] = Node(j, dist[i][j] );
  51.         }
  52.         sort( values[i].begin(), values[i].begin() + n);
  53. //        for( int j = 0; j < n; j++ )
  54. //        {
  55. //            cout<<values[i][j].index<<" "<<values[i][j].value<<endl;
  56. //        }
  57. //        cout<<endl<<endl;
  58.     }
  59.     ll d1, d2, d3;
  60.     dx = xs[0] - xs[1];
  61.     dy = ys[0] - ys[1];
  62.     d1 = dx*dx+dy*dy;
  63.     dx = xs[1] - xs[2];
  64.     dy = ys[1] - ys[2];
  65.     d2 = dx*dx+dy*dy;
  66.     dx = xs[2] - xs[0];
  67.     dy = ys[2] - ys[0];
  68.     d3 = dx*dx+dy*dy;
  69.     ll d2p, d3p;
  70.     vector<Node>::iterator low, up;
  71.     Node aux;
  72.     ll v;
  73.     set<ll> result;
  74.     for( int i = 0; i < n; i++ )
  75.     {
  76.         for( int j = 0; j < n; j++ )
  77.         {
  78.             if ( i == j ) continue;
  79.             d2p = d2*dist[i][j];
  80.             d3p = d3*dist[i][j];
  81.             if ( d2p % d1 != 0 ) continue;
  82.             if ( d3p % d1 != 0 ) continue;
  83.             d2p /= d1;
  84.             d3p /= d1;
  85.             low = lower_bound( values[j].begin(), values[j].begin()+n, Node(-1, d2p) );
  86.             up = upper_bound( values[j].begin(), values[j].begin()+n, Node(-1, d2p) );
  87.             while( low != up )
  88.             {
  89.                 aux = values[j][low-values[j].begin()];
  90.                 if ( aux.index != i && aux.index != j && dist[aux.index][i] == d3p )
  91.                 {
  92.  
  93.                     if ( i > j && i > aux.index )
  94.                     {
  95.                         v = i*f1;
  96.                         if ( j > aux.index )
  97.                         {
  98.                             v += j*f2;
  99.                             v += aux.index*f3;
  100.                         }
  101.                         else
  102.                         {
  103.                             v += aux.index*f2;
  104.                             v += j*f3;
  105.                         }
  106.                     }
  107.                     else if ( j > i && j > aux.index )
  108.                     {
  109.                         v = j*f1;
  110.                         if ( i > aux.index )
  111.                         {
  112.                             v += i*f2;
  113.                             v += aux.index*f3;
  114.                         }
  115.                         else
  116.                         {
  117.                             v += aux.index*f2;
  118.                             v += i*f3;
  119.                         }
  120.                     }
  121.                     else
  122.                     {
  123.                         v = aux.index*f1;
  124.                         if ( i > j )
  125.                         {
  126.                             v += i*f2;
  127.                             v += j*f3;
  128.                         }
  129.                         else
  130.                         {
  131.                             v += j*f2;
  132.                             v += i*f3;
  133.                         }
  134.                     }
  135.                     //cout<<i<<" "<<j<<" "<<aux.index<<" "<<v<<endl;
  136.                     result.insert(v);
  137.                 }
  138.  
  139.                 ++low;
  140.             }
  141.         }
  142.     }
  143.     cout<<result.size()<<"\n";
  144.  
  145.     }
  146. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement