• API
• FAQ
• Tools
• Archive
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.

Top