fork download
copy 
  1.  
  2. #include <bits/stdc++.h>
  3.  
  4. using namespace std;
  5.  
  6. #define int long long
  7. #define nn "\n"
  8. #define pi pair<int, int>
  9. #define fi first
  10. #define se second
  11. #define lb lower_bound
  12. #define ub upper_bound
  13. #define eb emplace_back
  14. #define pb push_back
  15. #define TASK "CACTAMGIAC"
  16.  
  17. #define ms(a, x) memset(a, x, sizeof(a))
  18. #define all(a) a.begin(), a.end()
  19. #define All(a, n) a + 1, a + 1 + n
  20.  
  21. #define LOG 19
  22.  
  23. const int INF = 1e18;
  24. const int mod = 1e9;
  25. const int N = 1005;
  26. const int MOD = 998244353;
  27.  
  28. struct Point{
  29.     int x, y;
  30. };
  31.  
  32. struct Triangle{
  33.     Point p[3];
  34. };
  35.  
  36. int n, par[N], sz[N];
  37. Triangle a[N];
  38. int find(int u){
  39.     if(par[u] == u) return u;
  40.     return par[u] = find(par[u]);
  41. }
  42. void unite(int u, int v){
  43.     u = find(u);
  44.     v = find(v);
  45.     if(u == v) return;
  46.     if(sz[u] < sz[v]) swap(u, v);
  47.     par[v] = u;
  48.     sz[u] += sz[v];
  49. }
  50. int cross(Point u, Point v, Point w){
  51.     return (v.x - u.x) * (w.y - u.y)
  52.          - (v.y - u.y) * (w.x - u.x);
  53. }
  54.  
  55. bool trenDoan(Point u, Point v, Point w){
  56.     return cross(u, v, w) == 0
  57.         && min(u.x, v.x) <= w.x
  58.         && w.x <= max(u.x, v.x)
  59.         && min(u.y, v.y) <= w.y
  60.         && w.y <= max(u.y, v.y);
  61. }
  62.  
  63. bool giaoNhau(Point u, Point v, Point s, Point t){
  64.     int c1 = cross(u, v, s);
  65.     int c2 = cross(u, v, t);
  66.     int c3 = cross(s, t, u);
  67.     int c4 = cross(s, t, v);
  68.     if(c1 == 0 && trenDoan(u, v, s)) return true;
  69.     if(c2 == 0 && trenDoan(u, v, t)) return true;
  70.     if(c3 == 0 && trenDoan(s, t, u)) return true;
  71.     if(c4 == 0 && trenDoan(s, t, v)) return true;
  72.     return ((c1 > 0 && c2 < 0) || (c1 < 0 && c2 > 0))
  73.         && ((c3 > 0 && c4 < 0) || (c3 < 0 && c4 > 0));
  74. }
  75. bool trongTamGiac(Point p, Triangle t){
  76.     int s1 = cross(t.p[0], t.p[1], p);
  77.     int s2 = cross(t.p[1], t.p[2], p);
  78.     int s3 = cross(t.p[2], t.p[0], p);
  79.     return (s1 >= 0 && s2 >= 0 && s3 >= 0) || (s1 <= 0 && s2 <= 0 && s3 <= 0);
  80. }
  81. bool lienThong(Triangle u, Triangle v){
  82.     for(int i = 0; i < 3; i++){
  83.         if(trongTamGiac(u.p[i], v)) return true;
  84.         if(trongTamGiac(v.p[i], u)) return true;
  85.     }
  86.     for(int i = 0; i < 3; i++){
  87.         for(int j = 0; j < 3; j++){
  88.             if(giaoNhau(u.p[i], u.p[(i + 1) % 3], v.p[j], v.p[(j + 1) % 3]))
  89.                 return true;
  90.         }
  91.     }
  92.     return false;
  93. }
  94. void nhap(){
  95.     cin >> n;
  96.     for(int i = 1; i <= n; i++){
  97.         for(int j = 0; j < 3; j++)
  98.             cin >> a[i].p[j].x >> a[i].p[j].y;
  99.     }
  100. }
  101. void solve(){
  102.     for(int i = 1; i <= n; i++){
  103.         par[i] = i;
  104.         sz[i] = 1;
  105.     }
  106.     for(int i = 1; i <= n; i++){
  107.         for(int j = i + 1; j <= n; j++){
  108.             if(lienThong(a[i], a[j]))
  109.                 unite(i, j);
  110.         }
  111.     }
  112.     int ans = 0;
  113.     for(int i = 1; i <= n; i++){
  114.         if(find(i) == i)
  115.             ans++;
  116.     }
  117.     cout << ans << nn;
  118. }
  119. signed main(){
  120.     if(fopen(TASK".INP", "r")){
  121.         freopen(TASK".INP", "r", stdin);
  122.         freopen(TASK".OUT", "w", stdout);
  123.     }
  124.     ios_base::sync_with_stdio(0);
  125.     cin.tie(0);
  126.     cout.tie(0);
  127.     nhap();
  128.     solve();
  129.     return (0 ^ 0);
  130. }
  131.  
Success #stdin #stdout 0.01s 5296KB
comments (?)
stdin
copy 
5
2 1 4 4 1 4
0 3 5 3 1 -2
-4 5 1 5 -2 1
-3 4 -1 4 -2 2
6 5 8 3 5 3
stdout
copy 
2
https://ideone.com/arCc1W
language:
C++14 (gcc 8.3)
created:
1 hour ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!