Chinaunix

标题: 关于qsort对double数组排序的怪异数据问题 [打印本页]

---

作者: lovelyarry    时间: 2007-04-09 17:54
标题: 关于qsort对double数组排序的怪异数据问题

1. #include <stdio.h>
   
2. #include <stdlib.h>
   
3. 
   
4. #define        GETY(a, b)        ((double)((a[3] - a[1]) * (b - a[0]) / (a[2] - a[0])) + a[1])
   
5. #define        MAX(a, b)        ((a) > (b)) ? (a) : (b)
   
6. #define        MIN(a, b)        ((a) < (b)) ? (a) : (b)
   
7. 
   
8. int        LINE2[32  * 1024][4];
   
9. double        LINE3[512 * 1024][7];
   
10. 
    
11. int cmp(const void *a, const void *b) {
    
12.         double        x, y;
    
13. 
    
14.         x = ((double *)a)[0];
    
15.         y = ((double *)b)[0];
    
16. 
    
17.         if( x > y )        return 1;
    
18.         if( x < y )        return -1;
    
19. 
    
20.         x = ((double *)a)[4];
    
21.         y = ((double *)b)[4];
    
22. 
    
23.         if( x > y )        return 1;
    
24.         if( x < y )        return -1;
    
25. 
    
26.         x = ((double *)a)[1];
    
27.         y = ((double *)b)[1];
    
28. 
    
29.         if( x > y )        return 1;
    
30.         if( x < y )        return -1;
    
31.         return 0;
    
32. }
    
33. 
    
34. int main() {
    
35.         int        C, L1, L2, L3, i, j, f, d, t;
    
36. 
    
37.         fscanf(stdin, "%d", &C);
    
38.         while(C--) {
    
39.                 fscanf(stdin, "%d %d", &L1, &L2);
    
40.                 for(i = 0, L3 = 0; i < L2; i++) {
    
41.                         fscanf(stdin, "%d %d %d %d", &LINE2[i][0], &LINE2[i][1], &LINE2[i][2], &LINE2[i][3]);
    
42. 
    
43.                         if(LINE2[i][0] > LINE2[i][2]) {
    
44.                                 t = LINE2[i][0];
    
45.                                 LINE2[i][0] = LINE2[i][2];
    
46.                                 LINE2[i][2] = t;
    
47.                                 t = LINE2[i][1];
    
48.                                 LINE2[i][1] = LINE2[i][3];
    
49.                                 LINE2[i][3] = t;
    
50.                         }
    
51. 
    
52.                         for(j = LINE2[i][0], f = 0; ; j++) {
    
53.                                 LINE3[L3][0] = (double)j;
    
54.                                 LINE3[L3][1] = GETY(LINE2[i], j);
    
55.                                 LINE3[L3][2] = (double)(j + 1);
    
56.                                 LINE3[L3][3] = GETY(LINE2[i], (j + 1));
    
57.                                 LINE3[L3][4] = MIN(LINE3[L3][1], LINE3[L3][3]);
    
58.                                 LINE3[L3][5] = MAX(LINE3[L3][1], LINE3[L3][3]);
    
59.                                 LINE3[L3][6] = (double)L3;
    
60. //printf("[%d]:[(%f,%f);(%f,%f)]\n", L3, LINE3[L3][0], LINE3[L3][1], LINE3[L3][2], LINE3[L3][3]);
    
61.                                 L3++;
    
62. 
    
63.                                 if(LINE2[i][2] == j + 1)
    
64.                                         break;
    
65.                         }
    
66.                 }
    
67. 
    
68.                 qsort(LINE3, L3, sizeof(LINE3[0]), cmp);
    
69. 
    
70. 
    
71.                 for(i = 1, d = 0; i < L3 - 1; i++) {
    
72.                         for(j = i + 1; j < L3; j++) {
    
73.                                 printf("[%d:%d]#[(%f,%f);(%f,%f)]#[(%f,%f);(%f,%f)][%f]", i, j, LINE3[i][0], LINE3[i][1], LINE3[i][2], LINE3[i][3], LINE3[j][0], LINE3[j][1], LINE3[j][2], LINE3[j][3], LINE3[j][6]);
    
74.                                 if((LINE3[i][5] <= LINE3[j][4])
    
75.                                         || (LINE3[i][0] < LINE3[j][0])) {
    
76.                                         printf(" break\n");
    
77.                                         break;
    
78.                                 }
    
79. 
    
80.                                 if((LINE3[i][1] > LINE3[j][1] && LINE3[i][3] < LINE3[j][3])
    
81.                                         || (LINE3[i][1] < LINE3[j][1] && LINE3[i][3] > LINE3[j][3])) {
    
82.                                         printf(" cross\n");
    
83.                                         d++;
    
84.                                 }
    
85.                                 else {
    
86.                                         printf(" none\n");
    
87.                                 }
    
88.                         }
    
89.                 }
    
90.                 printf("%d\n", d);
    
91.         }
    
92. }
    

复制代码

数据的数据量非常大，重定向到文件里面。
在32766行，出现了异常数据，不知道哪里来的。

1. 
   
2. [32765:32766]#[(0.000000,32765.000000);(1.000000,32765.000000)]#[(0.000000,32766.000000);(1.000000,32766.000000)][491505.000000] break
   
3. [32766:32767]#[(0.000000,32766.000000);(1.000000,32766.000000)]#[(0.000000,0.000000);(0.000000,0.000000)][0.000000] break
   
4. [32767:32768]#[(0.000000,0.000000);(0.000000,0.000000)]#[(0.000000,0.000000);(0.000000,0.000000)][0.000000] break
   

复制代码

[ 本帖最后由 lovelyarry 于 2007-4-9 19:32 编辑 ]

a.rar

2007-04-09 17:54 上传

点击文件名下载附件

8.19 KB, 下载次数: 17

测试数据

---

作者: emacsnw    时间: 2007-04-09 18:32
32767，这个数字很熟悉啊。。16位signed int的最大整数。会不会和这个有关？

---

欢迎光临 Chinaunix (http://bbs.chinaunix.net/)

Powered by Discuz! X3.2