0votos

Encuentra el Punto Óptimo en C

por josejuan hace 3 años

Usando arrays se obtiene una gran mejora cuando el radio es "pequeño", pero empieza a ser un problema si es muy grande, las soluciones anteriores son "inmunes" a este problema.

Buscar el punto dentro de un mapa que cumpla con los siguientes requerimientos.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
#include <stdio.h> 
#include <stdlib.h> 
#include <time.h> 
#include <string.h> 
 
typedef struct { int x1, x2, y; } Rango; // la y es >0 si entra o <0 si sale (no admitimos coordenadas y==0) 
 
int main(int argc, char **argv) { 
  int W = atoi(argv[1]); // ancho en píxeles del canvas 
  int R = atoi(argv[2]); // radio de la caja cerrada a contener el máximo de puntos 
  int N = atoi(argv[3]); // nº de puntos aleatorios para probar 
 
  printf("Ancho : %i\n", W); 
  printf("Radio : %i\n", R); 
  printf("Puntos: %i\n", N); 
 
  srand((unsigned) time(NULL)); 
 
  Rango *Y = (Rango *) malloc( sizeof(Rango) * 2 * N); // el de entrada y el de salida 
 
  // generamos N aleatorios 
  for(int i = 0; i < 2 * N; i += 2) { 
    int y = R + 1 + rand() % (W - 2 * R); 
    int x = R +     rand() % (W - 2 * R); 
    Y[i + 1].x1 = Y[i].x1 = x - R; 
    Y[i + 1].x2 = Y[i].x2 = x + R; 
    Y[i    ].y  =  y - R; 
    Y[i + 1].y  = -y - R; 
 
  int *Xc = (int *) malloc( sizeof(int) * W ); // contador en X 
  memset(Xc, 0, sizeof(int) * W); // a 0 
 
  // la ordenación es por Y pero quedan las últimas las de cierre de caja 
  int cmpY (const void * a, const void * b) { 
    int A = ((Rango *)a)->y, B = ((Rango *)b)->y; 
    int u = A > 0 ? A : -A, v = B > 0 ? B : -B; 
    if(u == v) { 
      if((A > 0) == (B > 0)) return 0; 
      return A > 0 ? 1 : -1; 
    return u - v; 
 
  qsort(Y, 2 * N, sizeof(Rango), cmpY); 
 
  int sN = 0, sT = 0; // máximo de cajas en algún punto y número de puntos que lo cumplen 
  for(int i = 0; i < 2 * N; i++) { 
    Rango r = Y[i]; 
    if(r.y > 0) { // entra caja 
      for(int j = r.x1; j < r.x2; j++) { 
        Xc[j]++; 
        if(Xc[j] == sN) sT++; // un punto más 
        if(Xc[j] >  sN) { sN = Xc[j]; sT = 1; } // mayor que otros 
    } else { // sale caja 
      for(int j = r.x1; j < r.x2; j++) Xc[j]--; 
 
  free(Xc); 
  free(Y); 
 
  printf("Contiene %i puntos y hay %i centroides\n", sN, sT); 
 
  return 0; 
 
/* 
 
Por ejemplo, en el siempre humilde Atom, con los parámetros indicados 
 
    centroid2$ gcc -O3 centroide.c -o centroide && time -f "%E, %M" ./centroide 1000 30 500000 
    Ancho : 1000 
    Radio : 30 
    Puntos: 500000 
    Contiene 2239 puntos y hay 2 centroides 
    0:01.62, 24624 
 
donde el coste básicamente es el de ordenar lass 1.000.000 coordenadas en Y. 
 
*/ 
1 comentario
0votos

Escrito por josejuan hace 3 años

Por ejemplo, aparte del obvio problema del espacio de memoria si la anchura es muy grande, aunque haya pocos puntos, toma
centroid2$ gcc -O3 centroide.c -o centroide && time -f "%E, %M" ./centroide 400000000 1000000 300
Ancho : 400000000
Radio : 1000000
Puntos: 300
Contiene 2 puntos y hay 5369809 centroides
0:11.19, 1244284


Mientras que las versiones anteriores no les afecta dicha anchura
centroide$ time -f "%E, %M" /home/josejuan/.local/bin/centroide-exe 400000000 1000000 300
Máx agregado size: 2, núm óptimos: 40
0:00.96, 5568

Comenta la solución

Tienes que identificarte para poder publicar tu comentario.