提交时间:2024-03-31 16:40:17
运行 ID: 27957
#include <bits/stdc++.h> using namespace std; typedef long long ll; const int N = 1009; struct node { int x, y; } a[N], b[N]; double dis(node x, node y) { ll dx = x.x - y.x, dy = x.y - y.y; return sqrtl(dx * dx + dy * dy); } int n, m, r[N]; namespace sub1 { struct DSU { int fa[N], tot; void init() { for (int i = 1; i <= n; i++) fa[i] = i; tot = n; } int get(int x) { while (x != fa[x]) x = fa[x] = fa[fa[x]]; return x; } void merge(int x, int y) { x = get(x), y = get(y); if (x != y) fa[y] = x, tot--; } } dsu; int sgn(int x) {return (x ? (x > 0 ? 1 : -1) : 0);} void Main() { dsu.init(); for (int i = 1; i <= n; i++) { for (int j = i + 1; j <= n; j++) { if (dsu.get(i) == dsu.get(j)) continue; int fl = 1; ll A = a[i].y - a[j].y, B = a[j].x - a[i].x; ll C = -(A * a[i].x + B * a[i].y); for (int k = 1; k <= m; k++) { ll T = A * b[k].x + B * b[k].y + C; if (T * T <= r[k] * r[k] * (A * A + B * B)) { ll _A = a[i].x - b[k].x, _B = a[i].y - b[k].y; ll _C = b[k].x * (b[k].x - a[i].x) + b[k].y * (b[k].y - a[i].y) - r[k] * r[k]; if (sgn(_A * a[i].x + _B * a[i].y + _C) != sgn(_A * a[j].x + _B * a[j].y + _C)) { fl = 0; break; } } } if (fl) dsu.merge(i, j); } } printf("%d\n", dsu.tot - 1); } } int main() { scanf("%d%d", &n, &m); for (int i = 1; i <= n; i++) { scanf("%d%d", &a[i].x, &a[i].y); } for (int i = 1; i <= m; i++) { scanf("%d%d%d", &b[i].x, &b[i].y, &r[i]); } sub1::Main(); return 0; }