ZOJ 1426 Counting Rectangles

枚举两条竖线之间同时与这两条竖线相交的横线的个数cnt，这两条竖线之间能组成矩形的个数为：从cnt中任选两条横线的方案个数。

将每两条竖线之间能组成矩形的个数加起来就是结果。

 1 #include <cstdio>
 2 #include <cstring>
 3 #include <cstdlib>
 4 #include <algorithm>
 5 #include <vector>
 6 
 7 using namespace std;
 8 
 9 const int MAXN = 110;
10 
11 struct MyLine
12 {
13     int st;
14     int ed;
15     int th;
16     MyLine() {}
17     MyLine( int _st, int _ed, int _th ): st(_st), ed(_ed), th(_th) { }
18 };
19 
20 vector<MyLine> hori;
21 vector<MyLine> vert;
22 bool ok[MAXN][MAXN];
23 
24 int solved()
25 {
26     int ans = 0;
27     int lenH = hori.size();
28     int lenV = vert.size();
29 
30     memset( ok, false, sizeof(ok) );
31 
32     for ( int i = 0; i < lenH; ++i )
33     {
34         for ( int j = 0; j < lenV; ++j )
35             if ( vert[j].th >= hori[i].st && vert[j].th <= hori[i].ed
36                 && hori[i].th >= vert[j].st && hori[i].th <= vert[j].ed ) ok[i][j] = true;
37     }
38 
39 
40     for ( int i = 0; i < lenH; ++i )
41     for ( int j = i + 1; j < lenH; ++j )
42     {
43         int cnt = 0;
44         for ( int k = 0; k < lenV; ++k )
45         if ( ok[i][k] && ok[j][k] ) ++cnt;
46         ans += cnt * (cnt - 1) / 2;
47     }
48 
49     return ans;
50 }
51 
52 int main()
53 {
54    // freopen( "input.txt", "r", stdin );
55     int T;
56     scanf( "%d", &T );
57     while ( T-- )
58     {
59         int N;
60         scanf( "%d", &N );
61         int x1, y1, x2, y2;
62         vert.clear();
63         hori.clear();
64         for ( int i = 0; i < N; ++i )
65         {
66             scanf( "%d%d%d%d", &x1, &y1, &x2, &y2 );
67             if ( x1 == x2 )
68             {
69                 if ( y1 > y2 ) swap( y1, y2 );
70                 hori.push_back( MyLine( y1, y2, x1 ) );
71             }
72             else if ( y1 == y2 )
73             {
74                 if ( x1 > x2 ) swap( x1, x2 );
75                 vert.push_back( MyLine( x1, x2, y1 ) );
76             }
77         }
78 
79         printf( "%d\n", solved() );
80     }
81     return 0;
82 }