yeputons

Untitled

Jun 9th, 2014
261
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 4.60 KB | None | 0 0
  1. #include <cstdio>
  2. #include <cstdlib>
  3. #include <cstring>
  4. #include <cassert>
  5. #include <ctime>
  6. #include <cmath>
  7. #include <algorithm>
  8. #include <string>
  9. #include <vector>
  10. #include <deque>
  11. #include <queue>
  12. #include <list>
  13. #include <set>
  14. #include <map>
  15. //#include <iostream>
  16.  
  17. #define pb push_back
  18. #define mp make_pair
  19. #define TASKNAME "guests"
  20.  
  21. #ifdef DEBUG
  22. #define eprintf(...) fprintf(stderr,__VA_ARGS__)
  23. #else
  24. #define eprintf(...)
  25. #endif
  26.  
  27. #define TIMESTAMP(x) eprintf("[" #x "] Time = %.3lfs\n",clock()*1.0/CLOCKS_PER_SEC)
  28.  
  29. #ifdef _WIN32
  30. #define LLD "%I64d"
  31. #else
  32. #define LLD "%lld"
  33. #endif
  34.  
  35. #define sz(x) ((int)(x).size())
  36.  
  37. using namespace std;
  38.  
  39. typedef long double ld;
  40. typedef long long ll;
  41. typedef vector<ll> vll;
  42. typedef vector<int> vi;
  43. typedef vector<vi> vvi;
  44. typedef vector<bool> vb;
  45. typedef vector<vb> vvb;
  46. typedef pair<int, int> pii;
  47. typedef pair <ll, ll> pll;
  48. typedef vector<pii> vpii;
  49.  
  50. const int inf = 1e9;
  51. const double eps = 1e-9;
  52. const int INF = inf;
  53. const double EPS = eps;
  54.  
  55. #ifdef DEBUG
  56. struct __timestamper {
  57.     ~__timestamper(){
  58.         TIMESTAMP(end);
  59.     }
  60. } __Timestamper;
  61. #else
  62. struct __timestamper {};
  63. #endif
  64.  
  65. /*Template end*/
  66.  
  67. const int tn = 1;
  68. const int h = 10;
  69. const int w = 10;
  70. vvb f;
  71.  
  72. int randint(int l, int r) {
  73.   int v = (rand() << 16) ^ rand();
  74.   v %= r - l + 1;
  75.   return l + abs(v);
  76. }
  77.  
  78. int sgn(int x) { return x < 0 ? -1 : !!x; }
  79. struct pt {
  80.   int x, y;
  81.   pt() : x(0), y(0) {}
  82.   pt(int _x, int _y) : x(_x), y(_y) {}
  83.   bool operator<(const pt &p2) const { return x != p2.x ? x < p2.x : y < p2.y; }
  84.   pt operator-(const pt &p2) const { return {x-p2.x,y-p2.y}; }
  85.   int operator*(const pt &p2) const { return sgn(x * p2.y - y * p2.x); }
  86. };
  87.  
  88. map<pt, vector<pt>> neigh;
  89. set<pt> was;
  90. vector<pt> seq;
  91.  
  92. void dfs_fill(pt p) {
  93.   if (was.count(p)) return;
  94.   if (p.x < 0 || p.y < 0 || p.x >= w || p.y >= h) return;
  95.   if (f[p.y][p.x]) return;
  96.   was.insert(p);
  97.   dfs_fill(pt(p.x - 1, p.y));
  98.   dfs_fill(pt(p.x + 1, p.y));
  99.   dfs_fill(pt(p.x, p.y - 1));
  100.   dfs_fill(pt(p.x, p.y + 1));
  101. }
  102.  
  103. void dfs(pt p) {
  104.   assert(!was.count(p));
  105.   was.insert(p);
  106.   seq.pb(p);
  107.   int cnt = 0;
  108.   for (auto b : neigh[p])
  109.     if (!was.count(b)) {
  110.       cnt++;
  111.       dfs(b);
  112.     }
  113.   assert(cnt <= 1);
  114. }
  115.  
  116. void gent(int prob)
  117. {
  118.   f = vvb(h, vb(w, false));
  119.   for (int y = 0; y < h; y++)
  120.   for (int x = 0; x < w; x++)
  121.     f[y][x] = randint(0, 99) < prob;
  122.  
  123.   for (;;) {
  124.     was.clear();
  125.     for (int y = 0; y < h; y++)
  126.       dfs_fill(pt(0, y)), dfs_fill(pt(w - 1, y));
  127.     for (int x = 0; x < w; x++)
  128.       dfs_fill(pt(x, 0)), dfs_fill(pt(x, h - 1));
  129.     for (int y = 0; y < h; y++)
  130.     for (int x = 0; x < w; x++)
  131.       f[y][x] = !was.count(pt(x, y));
  132.  
  133.     bool cont = false;
  134.     for (int y = 0; y + 1 < h; y++)
  135.     for (int x = 0; x + 1 < w; x++) {
  136.       if (f[y][x] != f[y][x + 1] && f[y][x] != f[y + 1][x] && f[y][x] == f[y + 1][x + 1]) {
  137.         f[y + 1][x] = !f[y + 1][x];
  138.         cont = true;
  139.       }
  140.     }
  141.     if (!cont) break;
  142.   }
  143.  
  144.   for (int y = h - 1; y >= 0; y--) {
  145.     for (int x = 0; x < w; x++)
  146.       eprintf("%c", ".#"[f[y][x]]);
  147.     eprintf("\n");
  148.   }
  149.   eprintf("\n");
  150.  
  151.   neigh.clear();
  152.   for (int y = 0; y < h; y++)
  153.   for (int x = 0; x < w; x++) if (f[y][x]) {
  154.     const int dx[] = { 1, 0, -1, 0 };
  155.     const int dy[] = { 0, 1, 0, -1 };
  156.  
  157.     const int px[] = { 1, 1, 0, 0, 1 };
  158.     const int py[] = { 0, 1, 1, 0, 0 };
  159.     for (int d = 0; d < 4; d++) {
  160.       int nx = x + dx[d], ny = y + dy[d];
  161.       if (nx >= 0 && nx < w && ny >= 0 && ny < h && f[ny][nx]) continue;
  162.  
  163.       pt a = { x + px[d    ], y + py[d    ] };
  164.       pt b = { x + px[d + 1], y + py[d + 1] };
  165.       neigh[a].pb(b);
  166.       neigh[b].pb(a);
  167.     }
  168.   }
  169.   for (auto &x : neigh) {
  170.     assert(sz(x.second) == 2);
  171.   }
  172.  
  173.   was.clear();
  174.   vector<vector<pt>> all;
  175.   for (auto &p : neigh) if (!was.count(p.first)) {
  176.     seq.clear();
  177.     dfs(p.first);
  178.     for (;;) {
  179.       bool cont = false;
  180.       for (int i = 0; i < sz(seq); i++) {
  181.         pt a = seq[(i + sz(seq) - 1) % sz(seq)];
  182.         pt b = seq[i];
  183.         pt c = seq[(i + 1) % sz(seq)];
  184.         if ((a - b) * (c - b) == 0) {
  185.           seq.erase(seq.begin() + i);
  186.           cont = true;
  187.         }
  188.       }
  189.       if (!cont) break;
  190.     }
  191.     all.pb(seq);
  192.   }
  193.  
  194.   printf("%d\n", sz(all));
  195.   for (auto &v : all) {
  196.     printf("%d", sz(v));
  197.     for (pt p : v)
  198.       printf(" %d %d", p.x, p.y);
  199.     printf("\n");
  200.   }
  201. }
  202.  
  203. int main() {
  204.   {
  205.     ll x;
  206.     asm("rdtsc" : "=A"(x));
  207.     srand(x);
  208.   }
  209.   for (int i = 0; i < tn; i++) {
  210.     gent(20 + randint(0, 60));
  211. //    gent(20 + 60 * (2 * i + 1) / (2 * tn));
  212.   }
  213. }
Add Comment
Please, Sign In to add comment