USACO MAR11 Bovine Bridge Battle

Problem 8: Bovine Bridge Battle [Richard Ho, 2007]

Each of Farmer John's N (4 <= N <= 1,000) cows is patiently waiting
in the main pasture with cow i at point with integer coordinates
(X_i, Y_i) (-1,000,000,000 <= X_i <= 1,000,000,000; -1,000,000,000
<= Y_i <= 1,000,000,000).

The cows wish to form into groups of four in order to play Bridge,
their new favorite card game. Each group must satisfy an important
constraint: four cows are allowed to team up if and only if there
exists some point X somewhere in the plane (and not coincident with
any of the four points of the potential group of four) such that
rotating any of the group's cows 180 degrees about that point X
gives the position of some other cow in the group.

Please help the cows determine the number of sets of four cows that
can form a Bridge group.

By way of example, suppose eight cows are standing at eight points:

                  |
                 f*
                  |             a = (-3, 1)    e = (-1, 1)
           b*     |             b = (-2, 2)    f = ( 0, 3)
        a      e  |             c = (-3, 0)    g = ( 2, 0)
         *     *  |             d = (-2, 0)    h = ( 3, 0)
         c  d     |     g  h
---------*--*-----+-----*--*---------
                  |

Then the three legal sets of four cows are {a, b, e, d} (they rotate
around point (-2, 1)), {b, c, e, f} (around the point (-1.5, 1.5)),
and {c, d, g, h} (around (0,0)).

The supplied locations of the cows given are all distinct, although
they are supplied in no particular order. Furthermore, the answer
will fit into a signed 32-bit integer.

PROBLEM NAME: rotsym

INPUT FORMAT:

* Line 1: A single integer: N

* Lines 2..N+1: Line i+1 contains two space-separated integers: X_i
        and Y_i

SAMPLE INPUT (file rotsym.in):

8
-3 0
-2 0
-1 1
0 3
2 0
-3 1
3 0
-2 2

OUTPUT FORMAT:

* Line 1: A single integer that is the number of sets of 4 cows that
        form valid groups for bridge.

SAMPLE OUTPUT (file rotsym.out):

3

**********************************************************************

显然，直接4个for嵌套是绝对超时的。题目要求转180度后对称，那么，我们可以求出每两点之间连线的中点坐标，如果两个线段的中点坐标相等，那么它们上面的4点就满足条件。

由于计算中点坐标时需要用到除以2的操作，因此可能造成0.5出现。由于我们需要的不是中点坐标，只要中点坐标相等的线段，因此除以2可以直接忽略。

本人最初使用Hash表把点映射到正整数，然后用数组cnt[i]记录以标号i的点为中点的线段条数。那么答案就是Sigma{cnt[i] * (cnt[i] - 1) / 2}。不过Hash表消耗的内存较大，超过了16MB的限制。后来改用排序后扫描的办法，就顺利通过了。

C语言: 高亮代码由发芽网提供

06 
07 #include <stdio.h>
08 #include <stdlib.h>
09 #include <string.h>
10 #include <math.h>
11 
12 typedef struct
13 {
14     long x,y;
15 }POINT;
16 
17 int N;
18 POINT pos[1002];
19 POINT c[1002 * 1002 / 2];
20 
21 int pcmp(const void *a,const void *b)
22 {
23     POINT *m,*n;
24     m = (POINT *)a;n = (POINT *)b;
25     if(m->x > n->x)    return 1;
26     if(m->x == n->x && m->y > n->y)    return 1;
27     return -1;
28 }
29 
30 void solve()
31 {
32     long i,j;
33     long ans = 0;
34     long t = 0;
35     for(i = 0;i < N;i ++)
36         for(j = 0;j < i;j ++)
37         {
38             c[t].x = (pos[i].x + pos[j].x);
39             c[t].y = (pos[i].y + pos[j].y);
40             t ++;
41         }
42     //sort and then figure how many are the same
43     qsort(c,t,sizeof(POINT),pcmp);
44     long cnt = 1;
45     for(i = 1;i < t;i ++)   //be careful with cnt here
46     {
47         if(c[i].x == c[i - 1].x && c[i].y == c[i - 1].y)
48             cnt ++;
49         else
50         {
51             ans += cnt * (cnt - 1) / 2;
52             cnt = 1;
53         }
54     }
55     printf("%ld\n",ans);
56 }
57 
58 int main()
59 {
60     freopen("rotsym.in","r",stdin);
61     freopen("rotsym.out","w",stdout);
62     scanf("%d\n",&N);
63     int i;
64     for(i = 0;i < N;i ++)
65         scanf("%ld%ld\n",&pos[i].x,&pos[i].y);
66     solve();
67     fclose(stdout);
68     return 0;
69 }