Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <cstdio>
- #include <cstdlib>
- #include <cstring>
- #include <cassert>
- #include <ctime>
- #include <cmath>
- #include <algorithm>
- #include <string>
- #include <vector>
- #include <deque>
- #include <queue>
- #include <list>
- #include <set>
- #include <map>
- //#include <iostream>
- #define pb push_back
- #define mp make_pair
- #define TASKNAME "guests"
- #ifdef DEBUG
- #define eprintf(...) fprintf(stderr,__VA_ARGS__)
- #else
- #define eprintf(...)
- #endif
- #define TIMESTAMP(x) eprintf("[" #x "] Time = %.3lfs\n",clock()*1.0/CLOCKS_PER_SEC)
- #ifdef _WIN32
- #define LLD "%I64d"
- #else
- #define LLD "%lld"
- #endif
- #define sz(x) ((int)(x).size())
- using namespace std;
- typedef long double ld;
- typedef long long ll;
- typedef vector<ll> vll;
- typedef vector<int> vi;
- typedef vector<vi> vvi;
- typedef vector<bool> vb;
- typedef vector<vb> vvb;
- typedef pair<int, int> pii;
- typedef pair <ll, ll> pll;
- typedef vector<pii> vpii;
- const int inf = 1e9;
- const double eps = 1e-9;
- const int INF = inf;
- const double EPS = eps;
- #ifdef DEBUG
- struct __timestamper {
- ~__timestamper(){
- TIMESTAMP(end);
- }
- } __Timestamper;
- #else
- struct __timestamper {};
- #endif
- /*Template end*/
- const int tn = 1;
- const int h = 10;
- const int w = 10;
- vvb f;
- int randint(int l, int r) {
- int v = (rand() << 16) ^ rand();
- v %= r - l + 1;
- return l + abs(v);
- }
- int sgn(int x) { return x < 0 ? -1 : !!x; }
- struct pt {
- int x, y;
- pt() : x(0), y(0) {}
- pt(int _x, int _y) : x(_x), y(_y) {}
- bool operator<(const pt &p2) const { return x != p2.x ? x < p2.x : y < p2.y; }
- pt operator-(const pt &p2) const { return {x-p2.x,y-p2.y}; }
- int operator*(const pt &p2) const { return sgn(x * p2.y - y * p2.x); }
- };
- map<pt, vector<pt>> neigh;
- set<pt> was;
- vector<pt> seq;
- void dfs_fill(pt p) {
- if (was.count(p)) return;
- if (p.x < 0 || p.y < 0 || p.x >= w || p.y >= h) return;
- if (f[p.y][p.x]) return;
- was.insert(p);
- dfs_fill(pt(p.x - 1, p.y));
- dfs_fill(pt(p.x + 1, p.y));
- dfs_fill(pt(p.x, p.y - 1));
- dfs_fill(pt(p.x, p.y + 1));
- }
- void dfs(pt p) {
- assert(!was.count(p));
- was.insert(p);
- seq.pb(p);
- int cnt = 0;
- for (auto b : neigh[p])
- if (!was.count(b)) {
- cnt++;
- dfs(b);
- }
- assert(cnt <= 1);
- }
- void gent(int prob)
- {
- f = vvb(h, vb(w, false));
- for (int y = 0; y < h; y++)
- for (int x = 0; x < w; x++)
- f[y][x] = randint(0, 99) < prob;
- for (;;) {
- was.clear();
- for (int y = 0; y < h; y++)
- dfs_fill(pt(0, y)), dfs_fill(pt(w - 1, y));
- for (int x = 0; x < w; x++)
- dfs_fill(pt(x, 0)), dfs_fill(pt(x, h - 1));
- for (int y = 0; y < h; y++)
- for (int x = 0; x < w; x++)
- f[y][x] = !was.count(pt(x, y));
- bool cont = false;
- for (int y = 0; y + 1 < h; y++)
- for (int x = 0; x + 1 < w; x++) {
- if (f[y][x] != f[y][x + 1] && f[y][x] != f[y + 1][x] && f[y][x] == f[y + 1][x + 1]) {
- f[y + 1][x] = !f[y + 1][x];
- cont = true;
- }
- }
- if (!cont) break;
- }
- for (int y = h - 1; y >= 0; y--) {
- for (int x = 0; x < w; x++)
- eprintf("%c", ".#"[f[y][x]]);
- eprintf("\n");
- }
- eprintf("\n");
- neigh.clear();
- for (int y = 0; y < h; y++)
- for (int x = 0; x < w; x++) if (f[y][x]) {
- const int dx[] = { 1, 0, -1, 0 };
- const int dy[] = { 0, 1, 0, -1 };
- const int px[] = { 1, 1, 0, 0, 1 };
- const int py[] = { 0, 1, 1, 0, 0 };
- for (int d = 0; d < 4; d++) {
- int nx = x + dx[d], ny = y + dy[d];
- if (nx >= 0 && nx < w && ny >= 0 && ny < h && f[ny][nx]) continue;
- pt a = { x + px[d ], y + py[d ] };
- pt b = { x + px[d + 1], y + py[d + 1] };
- neigh[a].pb(b);
- neigh[b].pb(a);
- }
- }
- for (auto &x : neigh) {
- assert(sz(x.second) == 2);
- }
- was.clear();
- vector<vector<pt>> all;
- for (auto &p : neigh) if (!was.count(p.first)) {
- seq.clear();
- dfs(p.first);
- for (;;) {
- bool cont = false;
- for (int i = 0; i < sz(seq); i++) {
- pt a = seq[(i + sz(seq) - 1) % sz(seq)];
- pt b = seq[i];
- pt c = seq[(i + 1) % sz(seq)];
- if ((a - b) * (c - b) == 0) {
- seq.erase(seq.begin() + i);
- cont = true;
- }
- }
- if (!cont) break;
- }
- all.pb(seq);
- }
- printf("%d\n", sz(all));
- for (auto &v : all) {
- printf("%d", sz(v));
- for (pt p : v)
- printf(" %d %d", p.x, p.y);
- printf("\n");
- }
- }
- int main() {
- {
- ll x;
- asm("rdtsc" : "=A"(x));
- srand(x);
- }
- for (int i = 0; i < tn; i++) {
- gent(20 + randint(0, 60));
- // gent(20 + 60 * (2 * i + 1) / (2 * tn));
- }
- }
Add Comment
Please, Sign In to add comment