|
|
back to boardHelp me! I have wa 1((( Posted by Denis 23 Nov 2007 00:04 #include <iostream> #include <fstream> #include <stdio.h> #include <string> #include <algorithm> using namespace std; class sset { public: int p, rank; }; sset a[1010]; void init (int n) { int i; for (i = 0; i < n; ++i) { a[i].p = i; a[i].rank = 0; } } int fset (int x) { if (x != a[x].p) { a[x].p = fset (a[x].p); } return a[x].p; } void sset_union (int x, int y) { if (a[x].rank < a[y].rank) { a[x].p = a[y].p; } else { a[y].p = a[x].p; if (a[x].rank == a[y].rank) { a[x].rank++; } } } int n; string v[1010]; int c[1010][4] = {0}; int arr[1010] = {0}; bool is_in (int i, int j) { int cd; cd = (c[i][0]-c[j][0])*(c[i][0]-c[j][0]) + (c[i][1]-c[j][1])*(c[i][1]-c[j][1]) + (c[i][2]-c[j][2])*(c[i][2]-c[j][2]); int rd = c[i][3]+c[j][3]; rd *= rd; return rd > cd; } int main () { //freopen ("a.in", "r", stdin); //freopen ("a.out", "w", stdout); int i, j; int di; int p, q; scanf ("%d", &n); init (n); for (i = 0; i < n; ++i) { scanf ("%d%d%d%d", &c[i][0], &c[i][1], &c[i][2], &c[i][3]); di = -1; for (j = i-1; j >= 0; --j) { if (is_in(i, j)) { p = fset (i); q = fset (j); sset_union (p, q); } } } for (i = 0; i < n; ++i) { j = fset(i); if (v[j] == "") { v[j] = (char)(i+'0'); } else { v[j] += ", "; v[j] += (char)(i+'0'); } } sort (v, v+n); for (i = 0; i < n; ++i) { if (v[i] != "") { cout<<v[i]<<endl; } } return 0; } |
|
|