Untitled
raw download clone
C
views 11
,
size 1018 b
12155
#include <stdio.h>
#include <math.h>

int n, r;
int one_count, count;
int x[10005], y[10005];

int visited[10005];
double dist[1005][1005];

void dfs(int now, int pa)
{
    int cnt = 0;
    visited[now] = 1;
    for (int i = 0;i < n;i++) {
        if (i == now) continue;
        if (i == pa) continue;
        if (visited[i] == 1) continue;
        if (dist[now][i] <= r) {
            dfs(i, now);
            cnt++;
        }
    }
    if ((cnt == 0) && (pa == -1)) one_count++;
}


int main(void)
{
    scanf("%d%d", &n, &r);
    for (int i = 0;i < n;i++) {
        scanf("%d%d", &x[i], &y[i]);
    }

    for (int i = 0;i < n;i++) {
        for (int j = 0;j < n;j++) {
            dist[i][j] = sqrt(pow(x[i] - x[j], 2) + pow(y[i] - y[j], 2));
        }
    }

    for (int i = 0;i < n;i++) {
        if (visited[i] == 0) {
            dfs(i, -1);
            count++;
        }
    }

    printf("%d %d\n", one_count, count - one_count);

    return 0;
}
close fullscreen
Login or Register to edit or fork this paste. It's free.