From c5fcf7179a83ef65c86c6a4a390029149e518649 Mon Sep 17 00:00:00 2001 From: Franciszek Malinka Date: Tue, 5 Oct 2021 21:49:54 +0200 Subject: Duzy commit ze smieciami --- Semestr 4/aisd/pracownia5/wzo.cpp | 286 -------------------------------------- 1 file changed, 286 deletions(-) delete mode 100644 Semestr 4/aisd/pracownia5/wzo.cpp (limited to 'Semestr 4/aisd/pracownia5/wzo.cpp') diff --git a/Semestr 4/aisd/pracownia5/wzo.cpp b/Semestr 4/aisd/pracownia5/wzo.cpp deleted file mode 100644 index 14056c8..0000000 --- a/Semestr 4/aisd/pracownia5/wzo.cpp +++ /dev/null @@ -1,286 +0,0 @@ -#include -using namespace std; - -#define VER_T 1 -#define HOR_T 0 - -#define BEG 0 -#define END 1 - -struct event { - int x, y, z; - bool t; - event(int _x=0, bool _t=false, int _y=0, int _z=0) : x(_x), y(_y), z(_z), t(_t) {} - - bool operator < (const event &e) const { - if (x == e.x) { - if (t == e.t) return make_pair(y, z) < make_pair(e.y, e.z); - if (t == HOR_T) return z == BEG; - if (e.t == HOR_T) return e.z == END; - return t < e.t; - // if (t == HOR_T && z == BEG) return true; - // else if (t == HOR_T) return false; - // else if (e.t == HOR_T && e.z == BEG) return false; - // else if (e.t == HOR_T) return true; - // return (make_pair(y,z) < make_pair(e.y, e.z)); - } - return x < e.x; - // return make_pair(x, make_pair(t, make_pair(y, z))) < make_pair(e.x, make_pair(e.t, make_pair(e.y, e.z))); - } - -}; - -struct pnt { - int x, y; - - pnt(int _x=0, int _y=0) : x(_x), y(_y) {} - - void transpoze(int a11, int a12, int a21, int a22) { - int temp = x*a11 + y*a12; - y = x*a21 + y*a22; - x = temp; - } - bool operator == (const pnt &p) { - return (x==p.x && y == p.y); - } - -}; - -struct seg { - pnt st, nd; - - seg(pnt p1=pnt(), pnt p2=pnt()) : st(p1), nd(p2) {} - - void transpoze(int a11, int a12, int a21, int a22) { - st.transpoze(a11, a12, a21, a22); - nd.transpoze(a11, a12, a21, a22); - } -}; - -inline int sig(int x) { - if (x < 0) return -1; - if (x == 0) return 0; - if (x > 0) return 1; -} - -void swap(pnt &x, pnt &y) { - swap(x.x, y.x); - swap(x.y, y.y); -} - -vector events; -map points; - -void get_cross_pnts(vector &result, vector &hor, vector &ver) { - events.resize(0); - points.clear(); - // cout << "h:\n"; - for (auto &s: hor) { - if (s.st.x > s.nd.x) swap(s.st, s.nd); - // cout << s.st.x << " " << s.st.y << ", " << s.nd.x << " " << s.nd.y << "\n"; - events.push_back(event(s.st.x, HOR_T, s.st.y, BEG)); - events.push_back(event(s.nd.x, HOR_T, s.st.y, END)); - } - // cout << "v:\n"; - for (auto &s: ver) { - if (s.st.y > s.nd.y) swap(s.st, s.nd); - // cout << s.st.x << " " << s.st.y << ", " << s.nd.x << " " << s.nd.y << "\n"; - - events.push_back(event(s.st.x, VER_T, s.st.y, s.nd.y)); - } - - sort(events.begin(), events.end()); - for (auto e: events) { - // cout << e.x << " " << (e.t == HOR_T ? "hor " : "ver ") << e.y << " " << (e.t == HOR_T ? (e.z == BEG ? "beg" : "end") : to_string(e.z)) << "\n"; - if (e.t == HOR_T) { - if (e.z == BEG) points[e.y]++; - else { - if (--points[e.y] == 0) points.erase(e.y); - } - } - else { - auto it = points.lower_bound(e.y); - while (it != points.end() && it->first <= e.z) { - result.push_back(pnt(e.x, it->first)); - it++; - } - } - } - // cout << "done\n"; -} - -vector temp; -vector hor, ver, cross_left, cross_right; - -void read() { - int n; - // cin >> n; - scanf("%d", &n); - for (int i = 0; i < n; i++) { - int x1, y1, x2, y2; - // cin >> x1 >> y1 >> x2 >> y2; - scanf("%d%d%d%d", &x1, &y1, &x2, &y2); - seg s = seg(pnt(x1, y1), pnt(x2, y2)); - if (y1 == y2) - hor.push_back(s); - else if (x1 == x2) - ver.push_back(s); - else if (sig(x1 - x2) == sig(y1 - y2)) - cross_right.push_back(s); - else - cross_left.push_back(s); - } -} - -void hor_ver(vector &result) { - // cout << "hor_ver\n"; - - temp.clear(); - get_cross_pnts(temp, hor, ver); - for (auto p: temp) result.push_back(p); -} - -void hor_c_r(vector &result) { - // cout << "hor_cr\n"; - temp.clear(); - for (auto &p: hor) p.transpoze(1, -1, 0, 1); - for (auto &p: cross_right) p.transpoze(1, -1, 0, 1); - get_cross_pnts(temp, hor, cross_right); - for (auto &p: hor) p.transpoze(1, 1, 0, 1); - for (auto &p: cross_right) p.transpoze(1, 1, 0, 1); - - for (auto &p: temp) { - p.transpoze(1, 1, 0, 1); - result.push_back(p); - } -} - -void hor_c_l(vector &result) { - // cout << "hor_cl\n"; - temp.clear(); - for (auto &p: hor) p.transpoze(1, 1, 0, 1); - for (auto &p: cross_left) p.transpoze(1, 1, 0, 1); - - get_cross_pnts(temp, hor, cross_left); - - for (auto &p: hor) p.transpoze(1, -1, 0, 1); - for (auto &p: cross_left) p.transpoze(1, -1, 0, 1); - - for (auto &p: temp) { - p.transpoze(1, -1, 0, 1); - result.push_back(p); - } -} - -void ver_c_r(vector &result) { - // cout << "ver_cr\n"; - - temp.clear(); - for (auto &p: ver) { - p.transpoze(1, 0, -1, 1); - } - for (auto &p: cross_right) { - p.transpoze(1, 0, -1, 1); - } - - get_cross_pnts(temp, cross_right, ver); - - for (auto &p: ver) { - p.transpoze(1, 0, 1, 1); - } - for (auto &p: cross_right) { - p.transpoze(1, 0, 1, 1); - } - - for (auto &p: temp) { - p.transpoze(1, 0, 1, 1); - result.push_back(p); - } -} - -void ver_c_l(vector &result) { - // cout << "ver_cl\n"; - - temp.clear(); - for (auto &p: ver) { - p.transpoze(-1, 0, 1, 1); - } - for (auto &p: cross_left) { - p.transpoze(-1, 0, 1, 1); - } - - get_cross_pnts(temp, cross_left, ver); - for (auto &p: ver) { - p.transpoze(-1, 0, 1, 1); - } - for (auto &p: cross_left) { - p.transpoze(-1, 0, 1, 1); - } - - for (auto &p: temp) { - p.transpoze(-1, 0, 1, 1); - result.push_back(p); - } -} - -void c_l_c_r(vector &result) { - temp.clear(); - // cout << "cl_cr\n"; - for (auto &p: cross_right) { - // cout << p.st.x << " " << p.st.y << ", " << p.nd.x << " " << p.nd.y << "\n"; - p.transpoze(1, 1, -1, 1); - } - // cout << "---\n"; - for (auto &p: cross_left) { - // cout << p.st.x << " " << p.st.y << ", " << p.nd.x << " " << p.nd.y << "\n"; - p.transpoze(1, 1, -1, 1); - } - - get_cross_pnts(temp, cross_right, cross_left); - - for (auto &p: ver) { - p.transpoze(1, -1, 1, 1); - } - for (auto &p: cross_left) { - p.transpoze(1, -1, 1, 1); - } - - for (auto &p: temp) { - p.transpoze(1, -1, 1, 1); - result.push_back(p); - } -} - -void solve() { - // cout << hor.size() << " " << ver.size() << " " << cross_left.size() << " " << cross_right.size() << "\n"; - vector result; - hor_ver(result); - hor_c_r(result); - hor_c_l(result); - ver_c_r(result); - ver_c_l(result); - for (auto &p: result) { - p.x *= 2; - p.y *= 2; - } - c_l_c_r(result); - - sort(result.begin(), result.end(), [&](const pnt &p1, const pnt &p2) { - if (p1.x == p2.x) return p1.y < p2.y; - return p1.x < p2.x; - }); - result.erase(unique(result.begin(), result.end()), result.end()); - for (auto p : result) { - printf("%d.%s ", p.x/2, (p.x % 2 == 1 ? "5" : "0")); - printf("%d.%s\n", p.y/2, (p.y % 2 == 1 ? "5" : "0")); - // cout << p.x/2 << "." << (p.x % 2 == 1 ? "5" : "0") << " "; - // cout << p.y/2 << "." << (p.y % 2 == 1 ? "5" : "0") << "\n"; - } -} - -int main() { - // ios_base::sync_with_stdio(false); - // cin.tie(); - read(); - solve(); -} \ No newline at end of file -- cgit v1.2.3