Advertisement
Guest User

Untitled

a guest
Dec 16th, 2012
167
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 3.79 KB | None | 0 0
  1. #define _CRT_SECURE_NO_WARNINGS
  2. #include <cstdio>
  3. #include <algorithm>
  4. #include <cstdlib>
  5. #include <ctime>
  6. #include <cstring>
  7. #include <map>
  8. #include <iostream>
  9. #include <algorithm>
  10. #include <functional>
  11. #include <vector>
  12.  
  13. #define TASK "snakes"
  14.  
  15. #ifdef WIN32
  16.     #define LLD "%I64u"
  17. #else
  18.     #define LLD "%llu"
  19. #endif
  20.  
  21. #define fill(a, x) memset(a, x, sizeof(a))
  22.  
  23. using namespace std;
  24.  
  25. typedef long long ll;
  26. typedef unsigned long long ull;
  27. #define maxn 3000
  28. #define maxh 110
  29.  
  30. struct point {
  31.     int x, y;
  32.     point nil () {
  33.         point res = {};
  34.         return res;
  35.     }
  36. };
  37.  
  38. vector < vector < int > > res;
  39. int n, m, k;
  40. int f[maxn][2];
  41. int op[maxh][maxh];
  42. int dist[maxn];
  43. int go[maxn][maxn];
  44. const int DX[8] = {1, 1, 1, 0, -1, -1, -1, 0};
  45. const int DY[8] = {1, 0, -1, -1, -1, 0, 1, 1};
  46. int q[maxn];
  47. int beg, en;
  48. int used[maxn];
  49. int edge[maxn][maxn];
  50. int num[maxn], mv[maxn];
  51. int cost[maxh][maxh];
  52.  
  53. bool inPoly(int x, int y, int id) {
  54.     int num = 0;
  55.     for (int kk = x + 1; kk <= m; ++kk)
  56.         if (op[kk][y] == id) num += max(cost[kk][y], -100);
  57.     return (num & 1);
  58. }
  59.  
  60. int main() {
  61. #ifdef _DEBUG
  62.     freopen("input.txt", "r", stdin);
  63.     freopen("output.txt", "w", stdout);
  64. #else
  65.     freopen(TASK".in", "r", stdin);
  66.     freopen(TASK".out", "w", stdout);
  67. #endif
  68.     cin >> m >> n >> k;
  69.     int numtest = 0;
  70.     do{
  71.     memset(op, 0, sizeof(op));
  72.     memset(go, 0, sizeof(go));
  73.     memset(used, 0, sizeof(used));
  74.     memset(num, 0, sizeof(num));
  75.     memset(mv, 0, sizeof(mv));
  76.     memset(cost, 0, sizeof(cost));
  77.     vector < point > curP;
  78.     point curpo;
  79.     for (int i = 1; i <= k; ++i) {
  80.         int nm;
  81.         cin >> nm;
  82.         curP.clear ();
  83.         for (int it = 1; it <= nm; ++it) {
  84.             int a, b;
  85.             cin >> a >> b;
  86.             curpo.x = a;
  87.             curpo.y = b;
  88.             curP.push_back (curpo);
  89.             op[a][b] = i;
  90.             f[i][0] = a; f[i][1] = b;
  91.         }
  92. //      cout << "i = " << i << endl;
  93.         for (int pp = 0; pp < nm; ++pp)
  94.             curP.push_back (curP[pp]);
  95.         for (int it = 1; it < nm + 1; ++it) {
  96. //          cout << curP[it].x << " " << curP[it].y << endl;
  97.             if (curP[it].x == curP[it - 1].x && curP[it].y > curP[it - 1].y ||
  98.                 curP[it].x == curP[it + 1].x && curP[it].y > curP[it + 1].y)
  99.                 cost[curP[it].x][curP[it].y] = 1;
  100.         }
  101.     }
  102.  
  103.     for (int i = 1; i <= m; ++i)
  104.         for (int j = 1; j <= n; ++j) {
  105.             for (int d = 0; d < 8; ++d) {
  106.                 if (op[i + DX[d]][j + DY[d]] != op[i][j])
  107.                     go[op[i + DX[d]][j + DY[d]]][op[i][j]] =
  108.                     go[op[i][j]][op[i + DX[d]][j + DY[d]]] = true;
  109.             }
  110.         }
  111.  
  112.     beg = 1; en = 0;
  113.     q[++en] = 0;
  114.     used[0] = true;
  115.     dist[0] = 0;
  116.     while(beg <= en) {
  117.         int cur = q[beg++];
  118.         used[cur] = true;
  119.         for (int i = 1; i <= k; ++i)
  120.             if (go[cur][i] && !used[i]) {
  121.                 q[++en] = i;
  122.                 used[i] = true;
  123.                 dist[i] = dist[cur] + 1;
  124.             }
  125.     }
  126.     memset(used, 0, sizeof(used));
  127.  
  128.     for (int i = 1; i <= k; ++i) {
  129.         for (int j = 1; j <= k; ++j)
  130.             if (go[i][j] && dist[j] == dist[i] + 1 && inPoly(f[j][0], f[j][1], i)) {
  131.                 ++num[i];
  132.                 edge[i][num[i]] = j;
  133.                 ++mv[j];
  134.             }
  135.     }
  136.    
  137. /*  for (int j = 1; j <= n; ++j) {
  138.         for (int i = 1; i <= m; ++i)
  139.             cout << cost[i][j] << "  ";
  140.         cout << endl;
  141.     }*/
  142.    
  143.    
  144.     for (int i = 1; i <= k; ++i)
  145.         if (num[i] > 1) {
  146.             for (int j = 1; j <= num[i]; ++j)
  147.                 --mv[edge[i][j]];
  148.             num[i] = 0;
  149.         }
  150.  
  151.     vector < int > tmp;
  152.     res.clear ();
  153.     for (int i = 1; i <= k; ++i)
  154.         if (!used[i] && mv[i] == 0) {
  155.             tmp.clear ();
  156.             int cur = i;
  157.             while (num[cur] == 1) {
  158.                 tmp.push_back (cur);
  159.                 used[cur] = true;
  160.                 cur = edge[cur][1];
  161.             }
  162.             tmp.push_back (cur);
  163.             used[cur] = true;
  164.             res.push_back (tmp);
  165.         }
  166.         //cout << "Test#:" << ++numtest << endl;
  167.     cout << res.size() << endl;
  168.     for (int i = 0; i < int (res.size ()); ++i) {
  169.         cout << res[i].size();
  170.         for (int j = 0; j < int (res[i].size ()); ++j)
  171.             cout << " " << res[i][j];
  172.         cout << endl;
  173.     }
  174.     cout << endl;
  175.     cerr << "ok" << endl;
  176.     }while(0);
  177.     return 0;
  178. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement