Inlay Cutters（模拟 + 枚举）

时间：2015-03-26 22:39:50 阅读：247 评论：0 收藏：0 [点我收藏+]

Inlay Cutters

Time Limit: 1000MS		Memory Limit: 65536K
Total Submissions: 2367		Accepted: 995

Description

The factory cuts rectangular M × N granite plates into pieces using a special machine that is able to perform cuts in 4 different directions: vertically, horizontally, and diagonally at the angle of 45 degrees to the sides of the plate. Every cut is a straight line that starts and ends on the side of the plate.
The factory has been ordered to produce tiles for the inlay, each tile of which is a 45 degrees right triangle. To reduce the time to deliver the tiles it was decided to take all triangles from the already cut plates. Information about all performed cuts is available and your task is to compute the number of triangles of any size that were produced.

Input

The input describes the cuts that were performed on a single rectangular plate. The first line of the input file contains three integer numbers M, N, and K, separated by spaces. M and N (1 ≤ M, N ≤ 50) are the dimensions of the plate, and K (0 ≤ K ≤ 296) is the number of cuts. Next K lines describe the cuts. ith cut is described by four integer numbers X_i,1, Y_i,1, X_i,2, and Y_i,2, separated by spaces, that represent the starting and ending point of the cut. Both starting (X_i,1, Y_i,1) and ending (X_i,2, Y_i,2) points of the cut are situated on the plate‘s border. Both points of the cut are different and the cut goes through the plate. Here, the coordinates by the X axis run from 0 to M, and the coordinates by the Y axis run from 0 to N. All cuts are different.

Output

Write to the output a single integer number - the number of triangles that were produced by the cuts.

Sample Input

Sample Output

Source

Northeastern Europe 2002

  1 #include<stdio.h>
  2 #include<string.h>
  3 #include<queue>
  4 using namespace std;
  5 int a[60 * 4][60 * 4] ;
  6 bool map[60 * 4][60 * 4] ;
  7 int col , row , cut ;
  8 int x1 , y1 , x2 , y2 ;
  9 int sum = 0 ;
 10 int move[][4] = {{-1,0,0,1},{-1,1,1,1},{0,1,1,0},{1,1,1,-1},{1,0,0,-1},{1,-1,-1,-1},{0,-1,-1,0},{-1,-1,-1,1}};
 11 
 12 void hua1 ()
 13 {
 14     for (int i = y1 ; i <= y2 ; i++) {
 15         a[x1][i] += 1 ;
 16     }
 17 }
 18 
 19 void hua2 ()
 20 {
 21     for (int i = x1 ; i <= x2 ; i++) {
 22         a[i][y1] += 1 ;
 23     }
 24 }
 25 
 26 void hua3 ()
 27 {
 28     int cnt = y2 - y1 + 1 ;
 29     int x = x1 , y = y1 ;
 30     while (cnt--) {
 31         a[x][y] += 1 ;
 32         x ++ , y ++ ;
 33     }
 34 }
 35 
 36 void hua4 ()
 37 {
 38     int cnt = x2 - x1 + 1 ;
 39     int x = x1 , y = y1 ;
 40     while (cnt--) {
 41         a[x][y] += 1 ;
 42         x ++ , y-- ;
 43     }
 44 }
 45 
 46 bool judge1 (int x1 ,int  y1 ,int  x2 ,int y2)
 47 {
 48     int cnt = x2 - x1 - 1 ;
 49     int x = x1 + 1 , y = y1 + 1 ;
 50     while (cnt --) {
 51         if (a[x][y] != 1  ) {
 52             return false ;
 53         }
 54         x ++ , y ++ ;
 55     }
 56     return true ;
 57 }
 58 
 59 bool judge2 (int x1 , int y1 , int x2 , int y2)
 60 {
 61     int cnt = x2 - x1 - 1 ;
 62     int x = x1 + 1 , y = y1 - 1 ;
 63     while (cnt--) {
 64         if (a[x][y] != 1) {
 65             return false ;
 66         }
 67         x++ , y-- ;
 68     }
 69     return true ;
 70 }
 71 
 72 bool judge3 (int x1 , int y1 , int x2 , int y2)
 73 {
 74     int cnt = x2 - x1 - 1 ;
 75     int x = x1 + 1 ;
 76     while (cnt--) {
 77         if (a[x][y1] != 1 ) {
 78             return false ;
 79         }
 80         x ++ ;
 81     }
 82     return true ;
 83 }
 84 
 85 bool judge4 (int x1 , int y1 , int x2 , int y2)
 86 {
 87     int cnt = y2 - y1 - 1 ;
 88     int y = y1 + 1 ;
 89     while (cnt --) {
 90         if (a[x1][y] != 1) {
 91             return false ;
 92         }
 93         y ++ ;
 94     }
 95     return true ;
 96 }
 97 
 98 void bfs (int sx , int sy)
 99 {
100    // printf ("sx = %d , sy = %d\n" , sx , sy) ;
101     for (int i = 0 ; i < 8 ; i++) {
102             int x1 = sx + move[i][0] , y1 = sy + move[i][1] ;
103             int x2 = sx + move[i][2] , y2 = sy + move[i][3] ;
104             if (x1 < 0 || y1 < 0 || x1 > row || y1 > col ) {
105                 continue ;
106             }
107             if (x2 < 0 || y2 < 0 || x2 > row || y2 > col ) {
108                 continue ;
109             }
110             if (a[x1][y1] * a[x2][y2] == 0 ) {
111                 continue ;
112             }
113             while(a[x1][y1] * a[x2][y2] == 1 ) {
114                 x1 += move[i][0] ;
115                 y1 += move[i][1] ;
116                 x2 += move[i][2] ;
117                 y2 += move[i][3] ;
118             }
119             if (a[x1][y1] * a[x2][y2] == 0 ) {
120                 continue ;
121             }
122             if (a[x1][y1] == 1 || a[x2][y2] == 1) {
123                 continue ;
124             }
125             if (x1 != x2) {
126                 int k = (y2 - y1) / (x2 - x1) ;
127                 if (k == 1) {
128                     if (x1 > x2) {
129                         x1 ^= x2 ^= x1 ^= x2 ;
130                         y1 ^= y2 ^= y1 ^= y2 ;
131                     }
132                     if (judge1 (x1 , y1 , x2 , y2) ) {
133                         sum ++ ;
134                     }
135                 }
136                 else if (k == -1) {
137                     if (x1 > x2) {
138                         x1 ^= x2 ^= x1 ^= x2 ;
139                         y1 ^= y2 ^= y1 ^= y2 ;
140                     }
141                     if ( judge2 (x1 , y1 , x2 , y2) ) {
142                         sum ++ ;
143                     }
144                 }
145                 else {
146                     if (x1 > x2) {
147                         x1 ^= x2 ^= x1 ^= x2 ;
148                     }
149                     if ( judge3 (x1 , y1 , x2 , y2) ) {
150                         sum ++ ;
151                     }
152                 }
153             }
154             else {
155                 if (y1 > y2) {
156                     y1 ^= y2 ^= y1 ^= y2 ;
157                 }
158                 if ( judge4 (x1 , y1 , x2 , y2) ) {
159                     sum ++ ;
160                 }
161             }
162         }
163 }
164 
165 int main ()
166 {
167     // freopen ("a.txt" , "r" , stdin ) ;
168     scanf ("%d%d%d" , &col , &row , &cut ) ;
169     col *= 4 , row *= 4 ;
170     for (int i = 0 ; i <= row ; i++) {
171         a[i][col] += 1 ;
172         a[i][0] += 1 ;
173     }
174     for (int i = 0 ; i <= col ; i++) {
175         a[row][i] += 1 ;
176         a[0][i] += 1 ;
177     }
178     while (cut--) {
179         scanf ("%d%d%d%d" , &y1 , &x1 , &y2 , &x2 ) ;
180         x1 *= 4 , y1 *= 4 , x2 *= 4 , y2 *= 4 ;
181         if (x1 == x2) {
182             if (y1 > y2) {
183                 y1 ^= y2 ^= y1^= y2 ;
184             }
185             hua1 () ;
186         }
187         else if (y1 == y2) {
188             if (x1 > x2) {
189                 x1 ^= x2 ^= x1 ^= x2 ;
190             }
191             hua2 () ;
192         }
193         else if ( (y2 - y1) / (x2 - x1) == 1) {
194             if (y1 > y2) {
195                 y1 ^= y2 ^= y1^= y2 ;
196                 x1 ^= x2 ^= x1 ^= x2 ;
197             }
198             hua3 () ;
199         }
200         else if ( (y2 - y1) / (x2 - x1) == -1 ) {
201             if (x1 > x2) {
202                 y1 ^= y2 ^= y1^= y2 ;
203                 x1 ^= x2 ^= x1 ^= x2 ;
204             }
205             hua4 () ;
206         }
207     }
208 
209    /* for (int i = 0 ; i <= row ; i++) {
210         for (int j = 0 ; j<= col ; j++) {
211             printf ("%d " , a[i][j]) ;
212         }
213         puts ("") ;
214     }*/
215 
216     for (int i = 0 ; i <= row ; i++) {
217         for (int j = 0 ; j <= col ; j++) {
218             if (a[i][j] > 1) {
219                 bfs (i , j) ;
220             }
221         }
222     }
223     printf ("%d\n" , sum ) ;
224 
225 }

View Code

Inlay Cutters（模拟 + 枚举）

原文：http://www.cnblogs.com/get-an-AC-everyday/p/4369951.html

踩

(0)

评论一句话评论（0）

分享档案

更多>

2021年09月23日 (328)
2021年09月24日 (313)
2021年09月17日 (191)
2021年09月15日 (369)
2021年09月16日 (411)
2021年09月13日 (439)
2021年09月11日 (398)
2021年09月12日 (393)
2021年09月10日 (160)
2021年09月08日 (222)