[others] Move other/colorec.* to mHoang and add other/{defrac,lang}.py

3 files changed, 121 insertions, 0 deletions

diff --git a/others/mHoang/README.md b/others/mHoang/README.md
index 05aa6bc..44574f8 100644
--- a/others/mHoang/README.md
+++ b/others/mHoang/README.md
@@ -73,3 +73,42 @@ Ghi ra thiết bị xuất chuẩn số đèn xanh sau lần bấm công tắc t
 | Sample Input | Sample Output |
 | :----------: | :-----------: |
 |       6      |       2       |
+
+## Hình chữ nhật bốn màu
+
+Trên mặt phẳng toạ độ Đề các vuông góc Oxy cho *n* điểm phân biệt
+*A<sub>i</sub>*(*x<sub>i</sub>*, *y<sub>i</sub>*), *i* = 1, 2, …, *n*. Mỗi điểm
+*A<sub>i</sub>* được tô bởi màu *c<sub>i</sub>* ∈ {1,2,3,4}. Ta gọi hình chữ
+nhật bốn màu là hình chữ nhật thoả mãn hai điều kiện sau:
+
+* Bốn đỉnh của hình chữ nhật là bốn điểm trong *n* điểm đã cho và được tô bởi
+  bốn màu khác nhau.
+* Các cạnh của hình chữ nhật song song với một trong hai trục toạ độ.
+
+### Yêu cầu
+
+Cho biết toạ độ và màu của *n* điểm, hãy đếm số lượng hình chữ nhật bốn màu.
+
+### Dữ liệu
+
+* Dòng đầu tiên chứa số nguyên dương *n* là số lượng điểm trên mặt phẳng.
+* Dòng thứ *i* trong *n* dòng tiếp theo chứa ba số nguyên *x<sub>i</sub>*,
+  *y<sub>i</sub>*, *c<sub>i</sub>* là thông tin về toạ độ và màu của điểm thứ 
+  *i*, *i* = 1, 2, …, *n*.
+
+*Các số trên cùng một dòng được ghi cách nhau ít nhất một dấu cách.*
+
+### Kết quả
+
+Một dòng chứa số lượng hình chữ nhật đếm được.
+
+### Giới hạn
+
+* 4 ≤ *n* ≤ 100000.
+* |*x<sub>i</sub>*|, |*y<sub>i</sub>*| ≤ 200.
+
+### Ví dụ
+
+|                              COLOREC.INP                              | COLOREC.OUT |
+| --------------------------------------------------------------------- | :---------: |
+| 7<br>0 0 1<br>0 1 4<br>2 1 2<br>2 -1 3<br>0 -1 1<br>-1 -1 4<br>-1 1 1 |      2      |
diff --git a/others/mHoang/colorec.pas b/others/mHoang/colorec.pas
new file mode 100644
index 0000000..a6931aa
--- /dev/null
+++ b/others/mHoang/colorec.pas
@@ -0,0 +1,54 @@
+type
+  pointtype = record
+    x, y: int16
+  end;
+
+var
+  f: text;
+  n, i, j: int32;
+  count: int32 = 0;
+  c, k: int8;
+  color: array[-200..200, -200..200] of int8;
+  points: array[1..4, 1..100000] of pointtype;
+  len: array[1..4] of int16 = (0, 0, 0, 0);
+
+function colorec(var a, b: pointtype): boolean;
+  begin
+    colorec := [color[a.x, b.y], color[b.x, a.y],
+                color[a.x, a.y], color[b.x, b.y]] = [1, 2, 3, 4]
+  end;
+
+begin
+  for i := -200 to 200 do
+    for j := -200 to 200 do
+      color[i, j] := 0;
+  assign(f, 'COLOREC.INP');
+  reset(f);
+  readln(f, n);
+  repeat
+    readln(f, i, j, c);
+    color[i, j] := c;
+    inc(len[c]);
+    points[c, len[c]].x := i;
+    points[c, len[c]].y := j
+  until eof(f);
+  close(f);
+
+  for k := 1 to 4 do
+    if len[k] <= n then
+      begin
+        c := k;
+        n := len[c]
+      end;
+  for i := 1 to n do
+    for k := 1 to 4 do
+      if k <> c then
+        for j := 1 to len[k] do
+          if colorec(points[c, i], points[k, j]) then
+            inc(count);
+
+  assign(f, 'COLOREC.OUT');
+  rewrite(f);
+  writeln(f, count);
+  close(f)
+end.
diff --git a/others/mHoang/colorec.py b/others/mHoang/colorec.py
new file mode 100755
index 0000000..d55ac7f
--- /dev/null
+++ b/others/mHoang/colorec.py
@@ -0,0 +1,28 @@
+#!/usr/bin/env python3
+from itertools import combinations
+
+COLORS = {1, 2, 3, 4}
+
+with open('COLOREC.INP') as f:
+    f.readline()
+    color, exes, eyes, count = {}, {}, {}, 0
+    for line in f:
+        x, y, c = map(int, line.split())
+        color[x, y] = c
+        exes.setdefault(y, [])
+        exes[y].append(x)
+        eyes.setdefault(x, [])
+        eyes[x].append(y)
+
+for v in eyes.values(): v.sort()
+for y0, l in exes.items():
+    for x0, x1 in combinations(l, 2):
+        s = COLORS - {color[x0, y0], color[x1, y0]}
+        if len(s) > 2: continue
+        for y1 in eyes[x0][y0:]:
+            try:
+                count += not s - {color[x0, y1], color[x1, y1]}
+            except:
+                continue
+
+with open('COLOREC.OUT', 'w') as f: print(count, file=f)