@@ -32,49 +32,79 @@ Output: 2
3232All points are distinct.
3333*/
3434
35+ #define HF 1021
36+
37+ typedef struct e_s {
38+ int y1 ;
39+ int y2 ;
40+ int x ;
41+ struct e_s * shadow ;
42+ }e_t ;
43+
44+ typedef struct {
45+ e_t * e [HF ];
46+ e_t buff [250000 ];
47+ int n ;
48+ }h_t ;
49+
50+ int hash_code (int y1 ,int y2 ) {
51+ int hc = y1 * 33 + y2 ;
52+ return hc %HF ;
53+ }
54+
55+ e_t * lookup (h_t * ht ,int y1 ,int y2 ) {
56+ int hc = hash_code (y1 ,y2 );
57+ e_t * e = ht -> e [hc ];
58+ while (e && (e -> y1 != y1 || e -> y2 != y2 ))e = e -> shadow ;
59+ return e ;
60+ }
61+
62+ void insert (h_t * ht ,int y1 ,int y2 ,int x ) {
63+ e_t * e = & ht -> buff [ht -> n ++ ];
64+ int hc = hash_code (y1 ,y2 );
65+ e -> y1 = y1 ;
66+ e -> y2 = y2 ;
67+ e -> x = x ;
68+ e -> shadow = ht -> e [hc ];
69+ ht -> e [hc ]= e ;
70+ }
71+
3572int cmp (const void * a ,const void * b ) {
36- int * p1 = * (int * * )a ;
37- int * p2 = * (int * * )b ;
38-
39- if (p1 [0 ]< p2 [0 ])return -1 ;
40- if (p1 [0 ]> p2 [0 ])return 1 ;
41- if (p1 [1 ]< p2 [1 ])return -1 ;
42- return 1 ;
73+ int * p1 = * (int * * )a ;
74+ int * p2 = * (int * * )b ;
75+
76+ if (p1 [0 ]< p2 [0 ])return -1 ;
77+ if (p1 [0 ]> p2 [0 ])return 1 ;
78+ if (p1 [1 ]< p2 [1 ])return -1 ;
79+ return 1 ;
4380}
44-
81+
4582int minAreaRect (int * * points ,int pointsSize ,int * pointsColSize ){
46- int * a ,* b ,* c ,* d ,area ,ans = 0 ;
47-
48- // x ascending, y ascending
49- qsort (points ,pointsSize ,sizeof (int * ),cmp );
50-
51- for (int i = 0 ;i < pointsSize ;i ++ ) {
52- a = points [i ];
53- for (int j = i + 1 ;j < pointsSize && points [j ][0 ]== a [0 ];j ++ ) {
54- b = points [j ];
55- for (int k = j + 1 ;k < pointsSize ;k ++ ) {
56- c = points [k ];
57- if (c [1 ]== a [1 ]) {
58- for (int l = k + 1 ;l < pointsSize && points [l ][0 ]== c [0 ];l ++ ) {
59- d = points [l ];
60- if (d [1 ]== b [1 ]) {
61- // this is a rectangle
62- area = (b [1 ]- a [1 ])* (c [0 ]- a [0 ]);
63- if (ans == 0 || ans > area )ans = area ;
64- gotonext ;
65- }
66- }
67-
68- }
69- next :
70- b = NULL ;
71- }
72- }
73-
74- return ans ;
83+ int i ,j ,x ,y1 ,y2 ,area ,ans = 0 ;
84+ e_t * e ;
85+ h_t ht = {0 };
86+
87+ // x ascending, y ascending
88+ qsort (points ,pointsSize ,sizeof (int * ),cmp );
89+
90+ for (int i = 0 ;i < pointsSize - 1 ;i ++ ) {
91+ x = points [i ][0 ];
92+ y1 = points [i ][1 ];
93+ for (j = i + 1 ;j < pointsSize && points [j ][0 ]== x ;j ++ ) {
94+ y2 = points [j ][1 ];
95+ e = lookup (& ht ,y1 ,y2 );
96+ if (e ) {
97+ area = (x - e -> x )* (y2 - y1 );
98+ if (ans == 0 || ans > area )ans = area ;
99+ e -> x = x ;
100+ }else {
101+ insert (& ht ,y1 ,y2 ,x );
102+ }
103+ }
104+ }
105+
106+ return ans ;
75107}
76-
77-
78108
79109
80110/*
