Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- using namespace std;
- typedef long long ll;
- mt19937 rnd(chrono::high_resolution_clock::now().time_since_epoch().count());
- const int N = 1407;
- int par[N], sz[N];
- int get(int v) {
- if (v == par[v]) {
- return v;
- } else {
- return par[v] = get(par[v]);
- }
- }
- void unite(int a, int b) {
- a = get(a), b = get(b);
- if (a != b) {
- if (sz[a] < sz[b]) swap(a, b);
- par[b] = a;
- sz[a] += sz[b];
- }
- }
- typedef long double ld;
- const ld eps = 1e-4;
- ld a[N], b[N], c[N];
- int main() {
- ios::sync_with_stdio(0);
- cin.tie(0);
- int n;
- cin >> n;
- for (int i = 0; i < n; i++) {
- par[i] = i;
- sz[i] = 1;
- }
- for (int i = 0; i < n; i++) {
- ld x1, y1, x2, y2, x3, y3;
- cin >> x1 >> y1 >> x2 >> y2 >> x3 >> y3;
- a[i] = (x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2);
- b[i] = (x1 - x3) * (x1 - x3) + (y1 - y3) * (y1 - y3);
- c[i] = (x2 - x3) * (x2 - x3) + (y2 - y3) * (y2 - y3);
- a[i] = sqrt(a[i]);
- b[i] = sqrt(b[i]);
- c[i] = sqrt(c[i]);
- }
- auto check = [&] (int i, int j) -> bool {
- ld kek_x = a[i] * (ld) b[i] * (ld) c[i];
- ld kek_y = a[j] * (ld) b[j] * (ld) c[j];
- {
- ld ax = a[i];
- ld ay = b[i];
- ld az = c[i];
- ld p = (ax + ay + az) / 2.0;
- p = p * (ld) (p - ax) * (ld) (p - ay) * (ld) (p - az);
- kek_y *= 4.0 * sqrt(p);
- }
- {
- ld ax = a[j];
- ld ay = b[j];
- ld az = c[j];
- ld p = (ax + ay + az) / 2.0;
- p = p * (ld) (p - ax) * (ld) (p - ay) * (ld) (p - az);
- kek_x *= 4.0 * sqrt(p);
- }
- if (fabs(kek_x - kek_y) < eps) {
- return true;
- } else {
- return false;
- }
- };
- for (int i = 0; i < n; i++) {
- for (int j = 0; j < n; j++) {
- if (check(i, j)) {
- unite(i, j);
- }
- }
- }
- int ans = 0;
- for (int i = 0; i < n; i++) {
- ans = max(ans, sz[i]);
- }
- cout << ans << '\n';
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement