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/gen.py | 40 ------ Semestr 4/aisd/pracownia5/wzo.cpp | 286 ------------------------------------- Semestr 4/aisd/pracownia5/wzo2.cpp | 184 ------------------------ 3 files changed, 510 deletions(-) delete mode 100644 Semestr 4/aisd/pracownia5/gen.py delete mode 100644 Semestr 4/aisd/pracownia5/wzo.cpp delete mode 100644 Semestr 4/aisd/pracownia5/wzo2.cpp (limited to 'Semestr 4/aisd/pracownia5') diff --git a/Semestr 4/aisd/pracownia5/gen.py b/Semestr 4/aisd/pracownia5/gen.py deleted file mode 100644 index 283cd04..0000000 --- a/Semestr 4/aisd/pracownia5/gen.py +++ /dev/null @@ -1,40 +0,0 @@ -import random -import sys - -random.seed(sys.argv[1]) - -n = int(sys.argv[2]) -maxcoord = 1000 - - -print(n) -for i in range(n): - ty = random.randint(0, 3) - a, b = 0, 0 - y1, y2 = 0, 0 - if ty == 0: - a = random.randint(0, maxcoord) - b = random.randint(a+1, maxcoord + 1) - y1 = random.randint(0, maxcoord) - y2 = y1 - if ty == 1: - y1 = random.randint(0, maxcoord) - y2 = random.randint(a+1, maxcoord + 1) - a = random.randint(0, maxcoord) - b = a - if ty == 2: - a = random.randint(0, maxcoord) - b = random.randint(0, maxcoord) - x = random.randint(1, maxcoord) - y1 = b - b = a + x - y2 = y1 + x - if ty == 3: - a = random.randint(0, maxcoord) - b = random.randint(0, maxcoord) - x = random.randint(1, maxcoord) - y1 = b - b = a + x - y2 = y1 - x - - print(a, y1, b, y2) 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 diff --git a/Semestr 4/aisd/pracownia5/wzo2.cpp b/Semestr 4/aisd/pracownia5/wzo2.cpp deleted file mode 100644 index b4e9ac3..0000000 --- a/Semestr 4/aisd/pracownia5/wzo2.cpp +++ /dev/null @@ -1,184 +0,0 @@ -#include -using namespace std; - -/* -[0 -1] -[1 0] -*/ - -struct pnt { - int x, y; - pnt (int _x=0, int _y=0) : x(_x), y(_y) {} - void transpose(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) const { - if (p.x == x) return y < p.y; - return x < p.x; - } - bool operator==(const pnt &p) const { - return (x == p.x && y == p.y); - } -}; - -struct seg { - pnt st, nd; - seg(pnt p1=pnt(), pnt p2=pnt()) : st(p1), nd(p2) {} - void transpose(int a11, int a12, int a21, int a22) { - st.transpose(a11, a12, a21, a22); - nd.transpose(a11, a12, a21, a22); - } -}; - -#define HOR_T 0 -#define VER_T 1 -#define CL_T 2 -#define CR_T 3 -#define BEG 0 -#define END 1 - -struct event { - int x; - int t; - int i1, i2; - - event(int _x, int _t, int _i1, int _i2) : x(_x), t(_t), i1(_i1), i2(_i2) {} - - bool operator < (const event &e) const { - if (x == e.x) { - if (t == e.t) return make_pair(i1, i2) < make_pair(e.i1, e.i2); - if (t == HOR_T) return (e.i2 == END); - if (e.t == HOR_T) return (i2 == BEG); - return t < e.t; - } - return x < e.x; - } -}; - -inline void swap(pnt &p1, pnt &p2) { - swap(p1.x, p2.x); - swap(p1.y, p2.y); -} - -vector segments; -vector result; -vector temp_res; -vector events; -map hor; -map cl; -map cr; - -void read() { - int n; - scanf("%d", &n); - segments.resize(n); - for (int i = 0; i < n; i++) { - cin >> segments[i].st.x >> segments[i].st.y >> segments[i].nd.x >> segments[i].nd.y; - } -} - -void rotate(int a11, int a12, int a21, int a22) { - for (auto s: segments) { - s.transpose(a11, a12, a21, a22); - } -} - -void solve_prob() { - temp_res.clear(); - events.clear(); - hor.clear(); cl.clear(); cr.clear(); - - for (auto s: segments) { - if (s.st.x > s.nd.x) swap(s.st, s.nd); - if (s.st.x == s.nd.x) { - if (s.st.y > s.nd.y) swap(s.st, s.nd); - events.push_back(event(s.st.x, VER_T, s.st.y, s.nd.y)); - } - else if (s.st.y == s.nd.y) { - 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)); - } - else if (s.st.y - s.nd.y < 0) { - events.push_back(event(s.st.x, CR_T, s.st.y, BEG)); - events.push_back(event(s.nd.x, CR_T, s.nd.y, END)); - } - else { - events.push_back(event(s.st.x, CL_T, s.st.y, BEG)); - events.push_back(event(s.nd.x, CL_T, s.nd.y, END)); - } - } - - sort(events.begin(), events.end()); - for (auto e: events) { - if (e.t == VER_T) { - auto it = hor.lower_bound(e.i1); - while (it != hor.end() && it->first <= e.i2) { - temp_res.push_back({e.x, it->first}); - it++; - } - it = cr.lower_bound(e.i1 - e.x); - while (it != cr.end() && it->first <= e.i2 - e.x) { - temp_res.push_back({e.x, it->first + e.x}); - it++; - } - it = cl.lower_bound(e.i1 + e.x); - while (it != cl.end() && it->first <= e.i2 + e.x) { - temp_res.push_back({e.x, it->first - e.x}); - it++; - } - } - if (e.t == CR_T) { - if (e.i2 == BEG) cr[e.i1 - e.x]++; - else if (--cr[e.i1 - e.x] <= 0) cr.erase(e.i1 - e.x); - } - if (e.t == CL_T) { - if (e.i2 == BEG) cl[e.i1 + e.x]++; - else if (--cl[e.i1 + e.x] <= 0) cl.erase(e.i1); - } - if (e.t == HOR_T) { - if (e.i2 == BEG) hor[e.i1]++; - else if (--hor[e.i1] <= 0) hor.erase(e.i1); - } - } -} - -void add_to_res(int a11, int a12, int a21, int a22) { - for (auto p: temp_res) { - p.transpose(a11, a12, a21, a22); - result.push_back(p); - } -} - -void solve() { - solve_prob(); - for (auto &p: temp_res) { - p.x *= 2; p.y *= 2; - } - add_to_res(1, 0, 0, 1); - for (auto &p: temp_res) { - p.x /= 2; p.y /= 2; - } - rotate(1, -1, 1, 1); - solve_prob(); - add_to_res(1, 1, -1, 1); - rotate(1, 1, -1, 1); - for (auto &p: temp_res) { - p.x /= 2; p.y /= 2; - } - - - - sort(result.begin(), result.end()); - result.erase(unique(result.begin(), result.end()), result.end()); - for (auto p : result) { - cout << p.x/2 << "." << (p.x % 2 == 1 ? "5" : "0") << " "; - cout << p.y/2 << "." << (p.y % 2 == 1 ? "5" : "0") << "\n"; - } -} - -int main() { - read(); - solve(); -} \ No newline at end of file -- cgit v1.2.3