From c5fcf7179a83ef65c86c6a4a390029149e518649 Mon Sep 17 00:00:00 2001
From: Franciszek Malinka <franciszek.malinka@gmail.com>
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/t.tin    |   0
 semestr-4/aisd/pracownia5/wzo.cpp  | 288 +++++++++++++++++++++++++++++++++++++
 semestr-4/aisd/pracownia5/wzo2.cpp | 184 ++++++++++++++++++++++++
 4 files changed, 512 insertions(+)
 create mode 100644 semestr-4/aisd/pracownia5/gen.py
 create mode 100644 semestr-4/aisd/pracownia5/t.tin
 create mode 100644 semestr-4/aisd/pracownia5/wzo.cpp
 create 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
new file mode 100644
index 0000000..85d332c
--- /dev/null
+++ b/semestr-4/aisd/pracownia5/gen.py
@@ -0,0 +1,40 @@
+import random
+import sys
+
+random.seed(sys.argv[1])
+
+n = int(sys.argv[2])
+maxcoord = 200
+
+
+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/t.tin b/semestr-4/aisd/pracownia5/t.tin
new file mode 100644
index 0000000..e69de29
diff --git a/semestr-4/aisd/pracownia5/wzo.cpp b/semestr-4/aisd/pracownia5/wzo.cpp
new file mode 100644
index 0000000..d4aa4fa
--- /dev/null
+++ b/semestr-4/aisd/pracownia5/wzo.cpp
@@ -0,0 +1,288 @@
+#include <bits/stdc++.h>
+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<event> events;
+map<int, int> points;
+
+void get_cross_pnts(vector<pnt> &result, vector<seg> &hor, vector<seg> &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<pnt> temp;
+vector<seg> 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<pnt> &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<pnt> &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<pnt> &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<pnt> &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<pnt> &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<pnt> &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<pnt> 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());
+
+  printf("%d\n", result.size());
+  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();
+}
diff --git a/semestr-4/aisd/pracownia5/wzo2.cpp b/semestr-4/aisd/pracownia5/wzo2.cpp
new file mode 100644
index 0000000..b4e9ac3
--- /dev/null
+++ b/semestr-4/aisd/pracownia5/wzo2.cpp
@@ -0,0 +1,184 @@
+#include <bits/stdc++.h>
+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<seg> segments;
+vector<pnt> result; 
+vector<pnt> temp_res;
+vector<event> events;
+map<int, int> hor;
+map<int, int> cl;
+map<int, int> 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