Advertisement
Guest User

Untitled

a guest
Apr 7th, 2020
279
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.93 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. typedef long long ll;
  6.  
  7. mt19937 rnd(chrono::high_resolution_clock::now().time_since_epoch().count());
  8.  
  9. const int N = 1407;
  10.  
  11. int par[N], sz[N];
  12.  
  13. int get(int v) {
  14.   if (v == par[v]) {
  15.     return v;
  16.   } else {
  17.     return par[v] = get(par[v]);
  18.   }
  19. }
  20.  
  21. void unite(int a, int b) {
  22.   a = get(a), b = get(b);
  23.   if (a != b) {
  24.     if (sz[a] < sz[b]) swap(a, b);
  25.     par[b] = a;
  26.     sz[a] += sz[b];
  27.   }
  28. }
  29.  
  30. typedef long double ld;
  31.  
  32. const ld eps = 1e-4;
  33.  
  34. ld a[N], b[N], c[N];
  35.  
  36. int main() {
  37.   ios::sync_with_stdio(0);
  38.   cin.tie(0);
  39.   int n;
  40.   cin >> n;
  41.   for (int i = 0; i < n; i++) {
  42.     par[i] = i;
  43.     sz[i] = 1;
  44.   }
  45.   for (int i = 0; i < n; i++) {
  46.     ld x1, y1, x2, y2, x3, y3;
  47.     cin >> x1 >> y1 >> x2 >> y2 >> x3 >> y3;
  48.     a[i] = (x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2);
  49.     b[i] = (x1 - x3) * (x1 - x3) + (y1 - y3) * (y1 - y3);
  50.     c[i] = (x2 - x3) * (x2 - x3) + (y2 - y3) * (y2 - y3);
  51.     a[i] = sqrt(a[i]);
  52.     b[i] = sqrt(b[i]);
  53.     c[i] = sqrt(c[i]);
  54.   }
  55.   auto check = [&] (int i, int j) -> bool {
  56.     ld kek_x = a[i] * (ld) b[i] * (ld) c[i];
  57.     ld kek_y = a[j] * (ld) b[j] * (ld) c[j];
  58.     {
  59.       ld ax = a[i];
  60.       ld ay = b[i];
  61.       ld az = c[i];
  62.       ld p = (ax + ay + az) / 2.0;
  63.       p = p * (ld) (p - ax) * (ld) (p - ay) * (ld) (p - az);
  64.       kek_y *= 4.0 * sqrt(p);
  65.     }
  66.     {
  67.       ld ax = a[j];
  68.       ld ay = b[j];
  69.       ld az = c[j];
  70.       ld p = (ax + ay + az) / 2.0;
  71.       p = p * (ld) (p - ax) * (ld) (p - ay) * (ld) (p - az);
  72.       kek_x *= 4.0 * sqrt(p);
  73.     }
  74.     if (fabs(kek_x - kek_y) < eps) {
  75.       return true;
  76.     } else {
  77.       return false;
  78.     }
  79.   };
  80.   for (int i = 0; i < n; i++) {
  81.     for (int j = 0; j < n; j++) {
  82.       if (check(i, j)) {
  83.         unite(i, j);
  84.       }
  85.     }
  86.   }
  87.   int ans = 0;
  88.   for (int i = 0; i < n; i++) {
  89.     ans = max(ans, sz[i]);
  90.   }
  91.   cout << ans << '\n';
  92.   return 0;
  93. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement