SHARE
TWEET

Graham's Scan (Andrew v.)

a guest Oct 21st, 2019 72 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <iostream>
  2. #include <algorithm>
  3. #include <vector>
  4. #include <cmath>
  5.  
  6. using namespace std;
  7.  
  8. struct punct {
  9.     double x, y;
  10.     void print_punct() {
  11.         cout << '(' << x << ", " << y << ')';
  12.     }
  13.     bool operator==(const punct& B) {
  14.         if (abs(x - B.x) < 0.000001 && abs(y - B.y) < 0.000001)
  15.             return true;
  16.         return false;
  17.     }
  18. };
  19.  
  20. bool cmp(punct& A, punct& B) {
  21.     if (A.x < B.x)
  22.         return true;
  23.     if (A.x > B.x)
  24.         return false;
  25.     if (A.y < B.y)
  26.         return true;
  27.     return false;
  28. }
  29.  
  30. bool viraj(vector <punct>& stiva) {
  31.     int n = stiva.size();
  32.     double x1 = stiva[n - 3].x, y1 = stiva[n - 3].y;
  33.     double x2 = stiva[n - 2].x, y2 = stiva[n - 2].y;
  34.     double x3 = stiva[n - 1].x, y3 = stiva[n - 1].y;
  35.     double det = x1 * y2 + x2 * y3 + x3 * y1 - x3 * y2 - x1 * y3 - x2 * y1;
  36.     if (det > 0)
  37.         return true;
  38.     return false;
  39. }
  40.  
  41. int main() {
  42.     vector <punct> A(4);
  43.     double a, b;
  44.     for (int i = 0; i < 4; i++) {
  45.         cin >> a >> b;
  46.         A[i].x = a;
  47.         A[i].y = b;
  48.     }
  49.  
  50.     sort(A.begin(), A.end(), cmp);
  51.     punct st = A[0], dr = A[3];
  52.     vector <punct> stiva;
  53.     stiva.push_back(A[0]);
  54.     stiva.push_back(A[1]);
  55.  
  56.     for (int i = 2; i < 4; i++) {
  57.         stiva.push_back(A[i]);
  58.         while (stiva.size() > 2 && !viraj(stiva)) {
  59.             stiva[stiva.size() - 2] = stiva[stiva.size() - 1];
  60.             stiva.pop_back();
  61.         }
  62.     }
  63.  
  64.     vector <punct> sol = stiva;
  65.     stiva.clear();
  66.     stiva.push_back(A[3]);
  67.     stiva.push_back(A[2]);
  68.     for (int i = 1; i >= 0; i--) {
  69.         stiva.push_back(A[i]);
  70.         while (stiva.size() > 2 && !viraj(stiva)) {
  71.             stiva[stiva.size() - 2] = stiva[stiva.size() - 1];
  72.             stiva.pop_back();
  73.         }
  74.     }
  75.  
  76.     for (int i = 1; i < stiva.size() - 1; i++)
  77.             sol.push_back(stiva[i]);
  78.  
  79.     cout << "Acoperirea convexa este: ";
  80.     for (auto &&el: sol) {
  81.         el.print_punct();
  82.         cout << ", ";
  83.     }
  84.  
  85.  
  86.     cout << "\nI = {\n";
  87.     if (sol.size() == 4) {
  88.         sol[0].print_punct();
  89.         cout << ", ";
  90.         sol[2].print_punct();
  91.         cout << "}\nJ = {\n";
  92.         sol[1].print_punct();
  93.         cout << ", ";
  94.         sol[3].print_punct();
  95.         cout << "}\n";
  96.     }
  97.     else {
  98.         for (auto &&el: sol) {
  99.             el.print_punct();
  100.             cout << ", ";
  101.         }
  102.         cout << "}\nJ = {\n";
  103.         bool found;
  104.         for (int i = 0; i < 4; i++){
  105.             found = false;
  106.             for (int j = 0; j < sol.size(); j++) {
  107.                 if (A[i] == sol[j]) {
  108.                     found = true;
  109.                     break;
  110.                 }
  111.             }
  112.             if (!found) {
  113.                 A[i].print_punct();
  114.                 cout << ", ";
  115.             }
  116.         }
  117.         cout << "}";
  118.     }
  119.  
  120.     return 0;
  121. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top