### Andrew Stankevich’s Contest #11解题报告 » ZOJ3370

ZOJ3370.cpp

```#include <cmath>
#include <cstdio>

const double EPS = 5e-7;
const int MAXN = 1234;

struct DisjointSet {
int p[MAXN];

void init(int n) {
for (int i = 1; i <= n; ++i) {
p[i] = i;
}
}

int root(int i) {
if (i > 0) {
return i == p[i] ? i : (p[i] = root(p[i]));
} else {
return -i == p[-i] ? i : -(p[-i] = root(p[-i]));
}
}

int _is(int i, int j, bool t) {
if (i < 0) {
i = -i;
t = !t;
}
if (j < 0) {
j = -j;
t = !t;
}
if (t) {
if (i == j) {
return 0;
}
p[j] = i;
} else {
if (i == j) {
return -1;
}
p[j] = -i;
}
return 0;
}

int istrue(int i, int j) {
return _is(root(i), root(j), true);
}

int isfalse(int i, int j) {
return _is(root(i), root(j), false);
}
} ds;

double d[MAXN][MAXN];

int main() {
int n, x[MAXN], y[MAXN];
double l, r, m;
bool flag;

while (scanf("%d", &n) != EOF) {
for (int i = 1; i <= n; ++i) {
scanf("%d%d", &x[i], &y[i]);
for (int j = 1; j < i; ++j) {
d[i][j] = hypot(y[i] - y[j], x[i] - x[j]);
}
}

l = 0;
r = 4e4;
while (r - l > EPS) {
m = (l + r) / 2;
flag = true;
ds.init(n);
for (int i = 1; flag && i <= n; ++i) {
for (int j = 1; flag && j < i; ++j) {
if (d[i][j] < m) {
flag &= ds.isfalse(i, j) != -1;
}
}
}
if (flag) {
l = m;
} else {
r = m;
}
}

ds.init(n);
for (int i = 1; i <= n; ++i) {
for (int j = 1; j < i; ++j) {
if (d[i][j] < l) {
ds.isfalse(i, j);
}
}
}
printf("%.10lf\n", l / 2);
for (int i = 1; i <= n; ++i) {
printf("%c%c", ds.root(i) > 0 ? '1' : '2', i == n ? '\n' : ' ');
}
}

return 0;
}

//real	0m0.498s
//user	0m0.476s
//sys	0m0.012s

// Run ID  	Submit Time  	Judge Status  	Problem ID  	Language  	Run Time(ms)  	Run Memory(KB)  	User Name  	Admin
// 180 	2010-07-08 14:42:37 	Accepted 	asc11i 	C++ 	950 	12080 	watashi@Zodiac 	Source
```