Facebook
From lit1numyt_, 7 Months ago, written in C++.
Embed
Download Paste or View Raw
Hits: 317
  1. #include <iostream>
  2. #include <cmath>
  3. #include <vector>
  4. #include <string>
  5. #include <algorithm>
  6.  
  7. #define no cout << "KHONG" << endl
  8. #define yes cout << step << endl
  9.  
  10. using namespace std;
  11.  
  12.     int step = 0;
  13.     int n, m;
  14.  
  15. struct POINT {
  16.     double x, y, z;
  17. };
  18.  
  19.     vector<POINT> points;
  20.  
  21. int compare(POINT a, POINT b) {
  22.     if (a.x < b.x) return -1;
  23.     else
  24.     if (a.x > b.x) return 1;
  25.     else
  26.  
  27.     if (a.y < b.y) return -1;
  28.     else
  29.     if (a.y > b.y) return 1;  
  30.     else
  31.  
  32.     if (a.z < b.z) return -1;
  33.     else
  34.     if (a.z > b.z) return 1;
  35.  
  36.     else return 0;
  37. }
  38.  
  39. void get_info() {
  40.     cin >> n;
  41.     POINT temp;
  42.     for (int i = 0; i < n; i++) {
  43.         cin >> temp.x >> temp.y >> temp.z;
  44.         points.push_back(temp);
  45.     }
  46. }
  47.  
  48. int BinSearch(vector<POINT> A, POINT a) {
  49.     int l = 0, r = n - 1, i;
  50.     while (l <= r) {
  51.         step++;
  52.         i = (r - l) / 2 + l;
  53.         if (compare(A[i], a) == 0) return i;
  54.         if (compare(A[i], a) == -1) l = i + 1;
  55.         if (compare(A[i], a) == 1) r = i - 1;
  56.  
  57.         //cout << "$$ " << l << " - " << r << " | " << i << endl;
  58.     }
  59.     return -1;
  60. }
  61.  
  62. void solve() {
  63.     step = 0;
  64.     POINT temp;
  65.     cin >> temp.x >> temp.y >> temp.z;
  66.     if (BinSearch(points, temp) == -1) no;
  67.     else yes;
  68. }
  69.  
  70. int main() {
  71.     get_info();
  72.     cin >> m;
  73.     for (int i = 0; i < m; i++) solve();
  74.    
  75.     return 0;
  76. }
  77.