Hướng dẫn giải của [VTT Q4 Contest 05] Bài 1: Hình chữ nhật đồng dạng [RECT]
Nộp một lời giải chính thức trước khi tự giải là một hành động có thể bị ban.
Hướng dẫn giải
Cho ~n~ hình chữ nhật, gom thành các nhóm đồng dạng (được phép xoay 90 độ), đếm số nhóm và cỡ nhóm lớn nhất.
Sub 1: So sánh từng cặp — ~O(n^2)~, dùng khi ~n \le 300~
Duyệt các hình chưa có nhóm; mỗi hình chưa có nhóm mở một nhóm mới, rồi quét các hình còn lại và kéo vào nhóm nếu đồng dạng. Để tránh số thực, kiểm tra bằng nhân chéo: ~a_i \cdot b_j = b_i \cdot a_j~ hoặc ~a_i \cdot a_j = b_i \cdot b_j~. Nếu chỉ nộp sub này: đúng 10/10 test (vì ~n \le 1000~ nên vẫn đủ nhanh).
Sub 2: Chuẩn hóa rồi sắp xếp — ~O(n \log n)~
Chia cả hai cạnh cho ước chung lớn nhất, rồi đặt cạnh nhỏ trước, cạnh lớn sau. Hai hình đồng dạng khi và chỉ khi cặp chuẩn hóa giống hệt nhau. Sắp xếp các cặp, những cặp bằng nhau nằm liền nhau nên đếm số đoạn và độ dài đoạn dài nhất. Nếu chỉ nộp sub này: đúng 10/10 test.
Chương trình hoàn chỉnh
Hàm main đọc dữ liệu, ~n \le 300~ gọi sub1, ngược lại gọi sub2. Khi đi thi nên viết như vậy: sub sau có sai hoặc chưa kịp làm thì vẫn ăn điểm sub trước.
#include <bits/stdc++.h>
using namespace std;
int n;
long long a[1005], b[1005];
// Sub 1: so sánh từng cặp bằng nhân chéo — O(n^2)
void sub1() {
vector<int> grp(n, -1);
int cnt = 0, best = 0;
for (int i = 0; i < n; i++) {
if (grp[i] != -1) continue;
cnt++;
int sz = 0;
for (int j = i; j < n; j++) {
if (grp[j] != -1) continue;
// đồng dạng: a_i/a_j = b_i/b_j hoặc a_i/b_j = b_i/a_j
if (a[i] * b[j] == b[i] * a[j] || a[i] * a[j] == b[i] * b[j]) {
grp[j] = cnt;
sz++;
}
}
best = max(best, sz);
}
cout << cnt << " " << best << "\n";
}
// Sub 2: rút gọn bằng gcd, đưa về dạng (nhỏ, lớn) rồi sắp xếp — O(n log n)
void sub2() {
vector<pair<long long, long long>> v;
for (int i = 0; i < n; i++) {
long long g = __gcd(a[i], b[i]);
long long x = a[i] / g, y = b[i] / g;
if (x > y) swap(x, y);
v.push_back({x, y});
}
sort(v.begin(), v.end());
int cnt = 0, best = 0;
for (int i = 0; i < n;) {
int j = i;
while (j < n && v[j] == v[i]) j++;
cnt++;
best = max(best, j - i);
i = j;
}
cout << cnt << " " << best << "\n";
}
int main() {
freopen("RECT.INP", "r", stdin);
freopen("RECT.OUT", "w", stdout);
ios::sync_with_stdio(false); cin.tie(nullptr);
cin >> n;
for (int i = 0; i < n; i++) cin >> a[i] >> b[i];
if (n <= 300) sub1();
else sub2();
}
Bình luận