Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #define _CRT_SECURE_NO_DEPRECATE
- #include <algorithm>
- #include <string>
- #include <set>
- #include <map>
- #include <vector>
- #include <queue>
- #include <iostream>
- #include <iterator>
- #include <cmath>
- #include <cstdio>
- #include <cstdlib>
- #include <sstream>
- #include <fstream>
- #include <ctime>
- #include <cstring>
- //#include <unordered_set>
- #pragma comment(linker, "/STACK:66777216")
- using namespace std;
- #define pb push_back
- #define ppb pop_back
- #define pi 3.1415926535897932384626433832795028841971
- #define mp make_pair
- #define x first
- #define y second
- #define aapii pair<int,int>
- #define pdd pair<double,double>
- #define INF 1000000000
- #define FOR(i,a,b) for (int _n(b), i(a); i <= _n; i++)
- #define FORD(i,a,b) for(int i=(a),_b=(b);i>=_b;i--)
- #define all(c) (c).begin(), (c).end()
- #define SORT(c) sort(all(c))
- #define rep(i,n) FOR(i,1,(n))
- #define rept(i,n) FOR(i,0,(n)-1)
- #define L(s) (int)((s).size())
- #define C(a) memset((a),0,sizeof(a))
- #define VI vector <int>
- #define ll long long
- #define TIME_LIMIT 3.85
- struct pii {
- int x, y;
- pii() : x(0), y(0) {}
- pii(int _x, int _y) : x(_x), y(_y) {}
- };
- inline bool operator <(const pii &a, const pii &b) {
- if (a.x != b.x) return a.x < b.x; else
- return a.y < b.y;
- }
- inline bool operator ==(const pii &a, const pii &b) {
- return a.x == b.x && a.y == b.y;
- }
- double getTime() {
- #ifndef LOCAL
- unsigned long long time;
- __asm__ volatile ("rdtsc" : "=A" (time));
- #ifndef ONLINE_JUDGE
- return time / 2.53e9;
- #else
- return time / 2.66e9;
- #endif
- #else
- return 1.0 * clock() / CLOCKS_PER_SEC;
- #endif
- }
- int a,b,c,d,i,j,n,m,k,w,h,ans, ssize, updated_ans;
- double startTime, lastStart;
- //vector<pii> scaled[101];
- pii scaled[101][1001];
- int len[101];
- int pr[201], st[201];
- pii cur[204];
- pii cord[101], best[101];
- pair<pii, pii> rcord[101];
- int nomsq[101];
- int ax[102], ay[102], nscale[102], orient[102];
- int bax[102], bay[102], bnscale[102], borient[102];
- int mem[102];
- int opt, bopt;
- bool used[101];
- bool RN, SW;
- inline void insert(int &k, int pos, pii val) {
- FORD(i, k, pos + 1) cur[i] = cur[i - 1];
- cur[pos] = val;
- ++k;
- }
- inline void erase(int &k, int pos) {
- FOR(i, pos, k - 2) {
- cur[i] = cur[i + 1];
- }
- --k;
- }
- inline void normalize(int &k) {
- while (1) {
- bool ok = 1;
- for (int i = 1; i < k - 1;) {
- if ((cur[i].x == cur[i - 1].x && cur[i].x == cur[i + 1].x) || (cur[i].y == cur[i - 1].y && cur[i].y == cur[i + 1].y)) {
- erase(k, i);
- continue;
- }
- ++i;
- }
- if (ok) break;
- }
- }
- int T = 0, CC = 0;
- char buf[101];
- inline char* toDouble(int a) {
- char *res = buf;
- if (a < 0) {
- *(res++) = '-';
- a = -a;
- }
- sprintf(res, "%d.%d", a / 10, a % 10);
- return res;
- }
- inline int getS(int v);
- inline pair<pii, pii> getCoord(int v);
- inline int markBad(int v) {
- pair<pii, pii> t1 = getCoord(v);
- int s = 0, num = -1;
- rept(i, ssize) {
- int w = st[i];
- if (!used[w]) continue;
- pair<pii, pii> t2 = rcord[w];
- int x1 = max(t1.x.x, t2.x.x);
- int y1 = max(t1.x.y, t2.x.y);
- int x2 = min(t1.y.x, t2.y.x);
- int y2 = min(t1.y.y, t2.y.y);
- if (x2 > x1 && y2 > y1) {
- num = w;
- ++s;
- }
- }
- if (s > 1) return -1; else
- if (s == 0) return -2; else
- return num;
- }
- inline void refresh() {
- memcpy(borient, orient, sizeof(borient));
- memcpy(best, cord, sizeof(best));
- memcpy(bax, ax, sizeof(bax));
- memcpy(bay, ay, sizeof(bay));
- memcpy(bnscale, nscale, sizeof(bnscale));
- }
- inline bool nudge() {
- memcpy(orient, borient, sizeof(borient));
- memcpy(cord, best, sizeof(best));
- memcpy(ax, bax, sizeof(bax));
- memcpy(ay, bay, sizeof(bay));
- memcpy(nscale, bnscale, sizeof(bnscale));
- opt = bopt;
- ssize = 0;
- VI xs, ys;
- rept(i, n) {
- if (best[i].x == -1) used[i] = 0; else
- used[i] = 1;
- rcord[i] = getCoord(i);
- if (used[i]) {
- st[ssize++] = i;
- xs.pb(rcord[i].x.x);
- xs.pb(rcord[i].y.x);
- //xs.pb(rcord[i].x.x + ax[i]);
- //xs.pb(rcord[i].y.x + ax[i]);
- ys.pb(rcord[i].x.y);
- ys.pb(rcord[i].y.y);
- //ys.pb(rcord[i].x.y + ay[i]);
- //ys.pb(rcord[i].y.y + ay[i]);
- }
- }
- rept(i, n) {
- if (used[i]) mem[i] = getS(i);
- }
- //cerr << rcord[3].x.x << " " << rcord[3].x.y << endl;
- SORT(xs); xs.resize(unique(all(xs)) - xs.begin());
- SORT(ys); ys.resize(unique(all(ys)) - ys.begin());
- random_shuffle(all(xs));
- if (L(xs) > 20) xs.resize(20);
- random_shuffle(all(ys));
- if (L(ys) > 20) ys.resize(20);
- int nadd = -1;
- pair<pii, pii> wt;
- int beg = ans;
- bool stop = 0;
- rept(i, L(xs)) {
- int x = xs[i];
- rept(j, L(ys)) {
- int y = ys[j];
- if (getTime() - startTime > 4.85) {
- stop = 1;
- break;
- }
- rept(i, n) {
- if (!used[i]) continue;
- rept(j, len[i]) {
- int cw = scaled[i][j].x, ch = scaled[i][j].y;
- if (ans - mem[i] + 2 * cw + 2 * ch <= ans) continue;
- int now = 1, cnt = 0;
- rept(z, 2) {
- if (z == 1) {
- swap(cw, ch);
- now *= -1;
- }
- if (x + cw > w || y + ch > h) {
- ++cnt;
- continue;
- }
- cord[i] = pii(x, y);
- rcord[i] = mp(pii(x, y), pii(x + cw, y + ch));
- nscale[i] = j;
- ax[i] = ay[i] = 0;
- orient[i] = now;
- int t = getS(i);
- int ns = ans - mem[i] + t;
- //cerr << ns << " " << beg << endl;
- if (ns > ans) {
- ans = ns;
- best[i] = cord[i];
- bnscale[i] = nscale[i];
- bax[i] = ax[i];
- bay[i] = bax[i];
- borient[i] = orient[i];
- rept(l, n) mem[l] = getS(l);
- //nadd = i;
- //wt = mp(pii(x, y), pii(j, now));
- } else {
- cord[i] = best[i];
- nscale[i] = bnscale[i];
- ax[i] = bax[i];
- ay[i] = bay[i];
- orient[i] = borient[i];
- rcord[i] = getCoord(i);
- }
- }
- if (cnt == 2) break;
- }
- }
- }
- if (stop) break;
- }
- /*if (nadd != -1) {
- used[nadd] = 1;
- cord[nadd] = wt.x;
- nscale[nadd] = wt.y.x;
- orient[nadd] = wt.y.y;
- ax[nadd] = ay[nadd] = 0;
- rept(l, n) if (!used[l]) cord[l] = pii(-1, -1);
- refresh();
- }*/
- if (ans == beg) return 0; else
- return 1;
- }
- inline bool nudge2() {
- memcpy(orient, borient, sizeof(borient));
- memcpy(cord, best, sizeof(best));
- memcpy(ax, bax, sizeof(bax));
- memcpy(ay, bay, sizeof(bay));
- memcpy(nscale, bnscale, sizeof(bnscale));
- opt = bopt;
- ssize = 0;
- VI xs, ys;
- rept(i, n) {
- if (best[i].x == -1) used[i] = 0; else
- used[i] = 1;
- rcord[i] = getCoord(i);
- if (used[i]) {
- st[ssize++] = i;
- xs.pb(rcord[i].x.x);
- xs.pb(rcord[i].y.x);
- //xs.pb(rcord[i].x.x + ax[i]);
- //xs.pb(rcord[i].y.x + ax[i]);
- ys.pb(rcord[i].x.y);
- ys.pb(rcord[i].y.y);
- //ys.pb(rcord[i].x.y + ay[i]);
- //ys.pb(rcord[i].y.y + ay[i]);
- }
- }
- rept(i, n) {
- if (used[i]) mem[i] = getS(i);
- }
- SORT(xs); xs.resize(unique(all(xs)) - xs.begin());
- SORT(ys); ys.resize(unique(all(ys)) - ys.begin());
- random_shuffle(all(xs));
- if (L(xs) > 20) xs.resize(20);
- random_shuffle(all(ys));
- if (L(ys) > 20) ys.resize(20);
- int nt = -1, nadd = -1;
- pair<pii, pii> wt;
- int beg = ans;
- bool stop = 0;
- rept(ii, L(xs)) {
- int x = xs[ii];
- rept(jj, L(ys)) {
- int y = ys[jj];
- if (getTime() - startTime > 4.85) {
- stop = 1;
- break;
- }
- rept(i, n) {
- if (used[i]) continue;
- rept(j, len[i]) {
- int cw = scaled[i][j].x, ch = scaled[i][j].y;
- if (beg + 2 * cw + 2 * ch <= ans) continue;
- int now = 1, cnt = 0;
- rept(z, 2) {
- if (z == 1) {
- swap(cw, ch);
- now *= -1;
- }
- if (x + cw > w || y + ch > h) {
- ++cnt;
- continue;
- }
- cord[i] = pii(x, y);
- rcord[i] = mp(pii(x, y), pii(x + cw, y + ch));
- nscale[i] = j;
- ax[i] = ay[i] = 0;
- orient[i] = now;
- int t = markBad(i);
- //if (t == -2) continue;
- if (t == -1) {
- ++cnt;
- continue;
- }
- int ns = beg;
- if (t != -2) ns -= mem[t];
- if (ns + 2 * cw + 2 * ch <= ans) continue;
- st[ssize++] = i;
- if (t != -2) used[t] = 0;
- ns += getS(i);
- //if (ns < 0) cerr << "HER" << endl;
- //if (ns >= 10000000) cerr << "HER" << endl;
- if (t != -2) used[t] = 1;
- --ssize;
- if (ns > ans) {
- ans = ns;
- nt = t;
- nadd = i;
- wt = mp(pii(x, y), pii(j, now));
- /*if (t != -2) used[t] = 0;
- used[i] = 1;
- cerr << (double)ns / 10 << endl;
- ans = ns;
- rept(l, n) if (!used[l]) cord[l] = pii(-1, -1);
- refresh();*/
- //return;
- }
- }
- if (cnt == 2) break;
- }
- }
- }
- if (stop) break;
- }
- if (nadd != -1) {
- if (nt >= 0) used[nt] = 0;
- used[nadd] = 1;
- cord[nadd] = wt.x;
- nscale[nadd] = wt.y.x;
- orient[nadd] = wt.y.y;
- ax[nadd] = ay[nadd] = 0;
- rept(l, n) if (!used[l]) cord[l] = pii(-1, -1);
- refresh();
- }
- if (ans == beg) return 0; else
- return 1;
- }
- bool nudge3() {
- memcpy(orient, borient, sizeof(borient));
- memcpy(cord, best, sizeof(best));
- memcpy(ax, bax, sizeof(bax));
- memcpy(ay, bay, sizeof(bay));
- memcpy(nscale, bnscale, sizeof(bnscale));
- opt = bopt;
- ssize = 0;
- VI xs, ys;
- rept(i, n) {
- if (best[i].x == -1) used[i] = 0; else
- used[i] = 1;
- rcord[i] = getCoord(i);
- if (used[i]) {
- st[ssize++] = i;
- xs.pb(rcord[i].x.x);
- xs.pb(rcord[i].y.x);
- //xs.pb(rcord[i].x.x + ax[i]);
- //xs.pb(rcord[i].y.x + ax[i]);
- ys.pb(rcord[i].x.y);
- ys.pb(rcord[i].y.y);
- //ys.pb(rcord[i].x.y + ay[i]);
- //ys.pb(rcord[i].y.y + ay[i]);
- }
- }
- rept(i, n) {
- if (used[i]) mem[i] = getS(i);
- }
- SORT(xs); xs.resize(unique(all(xs)) - xs.begin());
- SORT(ys); ys.resize(unique(all(ys)) - ys.begin());
- random_shuffle(all(xs));
- const int lf = 20;
- if (L(xs) > lf) xs.resize(lf);
- random_shuffle(all(ys));
- if (L(ys) > lf) ys.resize(lf);
- int nt = -1, nadd = -1;
- pair<pii, pii> wt;
- int beg = ans;
- bool stop = 0;
- int o = 0;
- rept(ii, L(xs)) {
- int x = xs[ii];
- rept(jj, L(ys)) {
- int y = ys[jj];
- if (stop || getTime() - startTime > 4.85) {
- stop = 1;
- break;
- }
- /*bool ok = 0;
- rept(i, n) {
- if (rcord[i].y.x == x && y >= rcord[i].x.y && y <= rcord[i].y.y) {
- ok = 1;
- break;
- }
- /*if (rcord[i].x == pii(x, y) || rcord[i].y == pii(x, y) || pii(rcord[i].x.x, rcord[i].y.y) == pii(x, y) || pii(rcord[i].y.x, rcord[i].x.y) == pii(x,y)) {
- ok = 1;
- break;
- }
- }
- if (!ok) continue;*/
- rept(i, n) {
- if ((i & 7) == 0) {
- if (getTime() - startTime > 4.85) {
- stop = 1;
- break;
- }
- }
- bool u = used[i];
- //if (!u) continue;
- int s = ans, old_mem = mem[i];
- if (u) s -= mem[i];
- used[i] = 0;
- //if (used[i]) continue;
- rept(j, len[i]) {
- int cw = scaled[i][j].x, ch = scaled[i][j].y;
- if (s + 2 * cw + 2 * ch <= ans) continue;
- int now = 1, cnt = 0;
- rept(z, 2) {
- if (z == 1) {
- swap(cw, ch);
- now *= -1;
- }
- if (x + cw > w || y + ch > h) {
- ++cnt;
- continue;
- }
- cord[i] = pii(x, y);
- rcord[i] = mp(pii(x, y), pii(x + cw, y + ch));
- nscale[i] = j;
- ax[i] = ay[i] = 0;
- orient[i] = now;
- int t = markBad(i);
- //if (t == -2) continue;
- if (t == -1) {
- ++cnt;
- continue;
- }
- int ns = s;
- if (t != -2) ns -= mem[t];
- if (ns + 2 * cw + 2 * ch <= ans) continue;
- st[ssize++] = i;
- if (t != -2) used[t] = 0;
- ns += getS(i);
- //if (ns < 0) cerr << "HER" << endl;
- //if (ns >= 10000000) cerr << "HER" << endl;
- if (t != -2) used[t] = 1;
- --ssize;
- if (ns > ans) {
- ans = ns;
- if (t != -2) used[t] = 0;
- used[i] = 1;
- u = 0;
- ssize = 0;
- rept(l, n) if (used[l]) st[ssize++] = l;
- rept(l, n) if (used[l]) {
- mem[l] = getS(l);
- }
- old_mem = mem[i];
- rcord[i] = getCoord(i);
- s = ans;
- //cerr << (double)ns / 10 << endl;
- ans = ns;
- rept(l, n) if (!used[l]) cord[l] = pii(-1, -1);
- refresh();
- //return;
- }
- }
- if (cnt == 2) break;
- }
- if (u) used[i] = 1;
- cord[i] = best[i];
- ax[i] = bax[i];
- ay[i] = bay[i];
- orient[i] = borient[i];
- nscale[i] = bnscale[i];
- rcord[i] = getCoord(i);
- mem[i] = old_mem;
- }
- }
- if (stop) break;
- }
- /*if (nadd != -1) {
- if (nt >= 0) used[nt] = 0;
- used[nadd] = 1;
- cord[nadd] = wt.x;
- nscale[nadd] = wt.y.x;
- orient[nadd] = wt.y.y;
- ax[nadd] = ay[nadd] = 0;
- rept(l, n) if (!used[l]) cord[l] = pii(-1, -1);
- refresh();
- }*/
- if (ans == beg) return 0; else
- return 1;
- }
- inline void out() {
- int fr = 0;
- rept(i, n) if (best[i].x == -1) ++fr;
- cerr << getTime() - startTime << " " << fr << " " << n << " " << (double)n * bopt / (w * h) << " " << T << endl;
- rept(i, n) {
- if (best[i].x == -1) {
- printf("-1 -1 -1 -1\n");
- continue;
- }
- int x1, y1, x2, y2;
- x1 = best[i].x; y1 = best[i].y;
- if (bax[i]) ++x1;
- if (bay[i]) ++y1;
- pii t = scaled[i][bnscale[i]];
- if (borient[i] == -1) swap(t.x, t.y);
- x2 = x1 + t.x; y2 = y1 + t.y;
- if (SW) {
- swap(x1, y1);
- swap(x2, y2);
- }
- printf("%s", toDouble(x1));
- printf(" %s", toDouble(y1));
- printf(" %s", toDouble(x2));
- printf(" %s\n", toDouble(y2));
- }
- exit(0);
- }
- inline pair<pii, pii> getCoord(int v) {
- int x1, y1, x2, y2;
- x1 = cord[v].x, y1 = cord[v].y;
- if (ax[v]) ++x1;
- if (ay[v]) ++y1;
- pii t = scaled[v][nscale[v]];
- if (orient[v] == -1) swap(t.x, t.y);
- x2 = x1 + t.x; y2 = y1 + t.y;
- return mp(pii(x1, y1), pii(x2, y2));
- }
- inline void sumXY(int x1, int y1, int x2, int y2, int &sx, int &sy) {
- //++CC;
- //CC += ssize;
- //if (ssize) CC += log((double)ssize) / log(2.0) * 3;
- sx = sy = 0;
- //rept(i, n) {
- rept(i, ssize) {
- int w = st[i];
- pair<pii, pii> t = getCoord(w);
- // sumY
- if (t.y.x == x1) {
- int l = max(y1, t.x.y);
- int r = min(y2, t.y.y);
- if (l < r) {
- if (orient[w] == 1) sy += r - l; else
- sy -= r - l;
- }
- }
- // sumX
- if (t.y.y == y1) {
- int l = max(x1, t.x.x);
- int r = min(x2, t.y.x);
- if (l < r) {
- if (orient[w] == 1) sx += r - l; else
- sx -= r - l;
- }
- }
- }
- }
- bool DEP;
- inline bool cmp(const pair<pii, pii> &a, const pair<pii, pii> &b) {
- if (abs(a.x.x - b.x.x) > 0) return a.x.x > b.x.x;
- pii t1 = scaled[a.x.y][a.y.x], t2 = scaled[b.x.y][b.y.x];
- int sa = t1.x * t1.y;
- int sb = t2.x * t2.y;
- if (sa != sb) return abs(sa - opt) < abs(sb - opt);
- //if (DEP) return a.y.x * len[b.x.y] < b.y.x * len[a.x.y];
- //if (DEP) return abs((double)a.y.x / len[a.x.y] - 0.5) < abs((double)b.y.x / len[b.x.y] - 0.5);
- //if (DEP) return (ll)sa * nomsq[a.x.y] < (ll)sb * nomsq[b.x.y];
- if (a.y.y >> 2) swap(t1.x, t1.y);
- if (b.y.y >> 2) swap(t2.x, t2.y);
- //return t1.x * t2.y > t2.x * t1.y;
- return t1.x > t2.x;
- }
- inline bool cmp2(const pair<pii, pii> &a, const pair<pii, pii> &b) {
- //++CC;
- if (abs(a.x.x - b.x.x) > 3) return a.x.x > b.x.x;
- if (a.x.y == b.x.y && a.y.x == b.y.x) {
- if ((a.y.y & 4) == (b.y.y & 4)) return 0;
- if (scaled[a.x.y][a.y.x].x > scaled[a.x.y][a.y.x].y) return (a.y.y >> 2) ^ 1; else
- return (a.y.y >> 2);
- }
- pii t1 = scaled[a.x.y][a.y.x], t2 = scaled[b.x.y][b.y.x];
- int sa = t1.x * t1.y;
- int sb = t2.x * t2.y;
- if (a.y.y >> 2) swap(t1.x, t1.y);
- if (b.y.y >> 2) swap(t2.x, t2.y);
- //if (sa == sb) return t1.x * t2.y > t2.x * t1.y;
- //if (DEP && sa == sb) return a.y.x * len[b.x.y] < b.y.x * len[a.x.y];
- if (sa == sb) return t1.x * t2.y > t2.x * t1.y;
- if (sa < opt || sb < opt) return sa > sb; else
- return sa < sb;
- }
- inline int getS(int v) {
- pair<pii, pii> t1 = getCoord(v);
- int s = 0;
- rept(i, ssize) {
- int w = st[i];
- if (!used[w] || w == v) continue;
- pair<pii, pii> t2 = rcord[w];
- int x1 = max(t1.x.x, t2.x.x);
- int y1 = max(t1.x.y, t2.x.y);
- int x2 = min(t1.y.x, t2.y.x);
- int y2 = min(t1.y.y, t2.y.y);
- if (x2 > x1 && y2 > y1) {
- return -INF;
- }
- int add = 0;
- if (x1 < x2 && y1 == y2) {
- add = x2 - x1;
- if (orient[w] == orient[v]) s -= add; else
- s += add;
- }
- if (y1 < y2 && x1 == x2) {
- add = y2 - y1;
- if (orient[w] == orient[v]) s -= add; else
- s += add;
- }
- }
- return s;
- }
- double lastUpdate;
- bool EX;
- const double limit = 2.0;
- int iter = 0;
- void rec(int s = 0, int depth = 0) {
- ++T;
- int bt = T;
- if (s > updated_ans) updated_ans = s;
- if (s > ans) {
- iter = 0;
- ans = s;
- bopt = opt;
- lastUpdate = getTime();
- rept(i, n) {
- if (used[i]) {
- best[i] = cord[i];
- bax[i] = ax[i];
- bay[i] = ay[i];
- borient[i] = orient[i];
- bnscale[i] = nscale[i];
- } else
- best[i] = pii(-1, -1);
- }
- }
- double currentTime = getTime();
- if (currentTime - startTime > 4.85) {
- out();
- }
- if (currentTime - startTime > limit) {
- return;
- }
- if (currentTime - lastUpdate > 0.05) {
- //EX = 1;
- return;
- }
- ++iter;
- if (iter > 1000) return;
- if (k == 2) return;
- pii t = pii(INF, INF);
- int v = -1;
- rep(i, k - 2) {
- if (cur[i] < t) {
- t = cur[i];
- v = i;
- }
- }
- if (v == -1) return;
- if (cur[v].x >= w - 1 || cur[v].y >= h - 1) return;
- int can = s;
- int rx = 0, ry = 0;
- int sq = 0;
- rept(i, k - 1) {
- sq += cur[i].x * cur[i + 1].y - cur[i].y * cur[i + 1].x;
- if (!cur[i].x && !cur[i + 1].x) continue;
- if (!cur[i].y && !cur[i + 1].y) continue;
- if (cur[i].y == h && cur[i + 1].y == h) continue;
- }
- sq += 0 * cur[0].y - h * cur[0].x;
- if (sq < 0) sq = -sq;
- int per = 0, sum = 0;
- rept(i, n) {
- if (used[i]) continue;
- FORD(j, len[i] - 1, 0) {
- if (min(scaled[i][j].x, scaled[i][j].y) + cur[v].x > w) continue;
- if (scaled[i][j].x * scaled[i][j].y * 2 + sq > 2 * w * h) continue;
- per += scaled[i][j].x + scaled[i][j].y;
- ry = max(ry, min(scaled[i][j].x, scaled[i][j].y));
- break;
- }
- }
- int add = 2 * per - ry;
- can += add;
- if (can <= ans) return;
- int old_k = k, old_s = s;
- pair<pii, int> old_cur[204];
- memcpy(old_cur, cur, k * sizeof(pii));
- // insert
- int maxh = cur[v - 1].y - cur[v].y;
- int maxw = w - cur[v].x;
- int min_right = cur[v + 1].x - cur[v].x;
- if (v - 2 >= 0) min_right = min(min_right, cur[v - 2].x - cur[v - 1].x);
- int cnt = 0;
- pair<pii, pii> cool = mp(pii(-1, -1), pii(-1, -1));
- if (depth <= n / 8) DEP = 1; else
- DEP = 0;
- rept(i, n) {
- if (used[i]) continue;
- ++cnt;
- FORD(j, len[i] - 1, 0) {
- int cw = scaled[i][j].x, ch = scaled[i][j].y;
- if (s + 2 * cw + 2 * ch < cool.x.x) continue;
- int now = 1;
- rept(z, 2) {
- if (z == 1) {
- now = -now;
- swap(cw, ch);
- }
- if (cw > maxw || ch > maxh) continue;
- if (s + 2 * cw + ch < cool.x.x) continue;
- int dx = 0, dy = 0;
- int sx = 0, sy = 0;
- sumXY(cur[v].x, cur[v].y, cur[v].x + cw, cur[v].y + ch, sx, sy);
- if (sy * now > 0) dx = 1;
- if (sx * now > 0) dy = 1;
- if (cur[v].x + cw + dx > w || cur[v].y + ch + dy > h) continue;
- if (ch + dy < maxh) {
- cord[i] = cur[v];
- nscale[i] = j;
- orient[i] = now;
- ax[i] = dx; ay[i] = dy;
- used[i] = 1;
- int ns = s + getS(i);
- used[i] = 0;
- if (ns > s || !s) {
- pair<pii, pii> cand = mp(pii(ns, i), pii(j, (z << 2) | (dx << 1) | dy));
- if (cool.x.x == -1 || cmp(cand, cool)) cool = cand;
- }
- } else {
- cord[i] = cur[v];
- nscale[i] = j;
- orient[i] = now;
- ax[i] = dx; ay[i] = dy;
- used[i] = 1;
- int ns = s + getS(i);
- used[i] = 0;
- if (ns > s || !s) {
- pair<pii, pii> cand = mp(pii(ns, i), pii(j, (z << 2) | (dx << 1) | dy));
- if (cool.x.x == -1 || cmp(cand, cool)) cool = cand;
- }
- }
- s = old_s;
- }
- }
- }
- if (!cnt) return;
- int ms = INF;
- if (cool.x.x != -1) {
- int i = cool.x.y;
- int j = cool.y.x;
- int z = cool.y.y >> 2;
- int cw = scaled[i][j].x, ch = scaled[i][j].y;
- int now = 1;
- if (z == 1) {
- now = -now;
- swap(cw, ch);
- }
- int dx = 0, dy = 0;
- dx = (cool.y.y >> 1) & 1;
- dy = (cool.y.y & 1);
- if (ch + dy < maxh) {
- cord[i] = cur[v];
- nscale[i] = j;
- orient[i] = now;
- ax[i] = dx; ay[i] = dy;
- used[i] = 1;
- s += getS(i);
- used[i] = 0;
- rcord[i] = getCoord(i);
- int ovp1 = cur[v + 1].x;
- cur[v] = pii(cur[v].x, cur[v].y + dy + ch);
- insert(k, v + 1, pii(cur[v].x + dx + cw, cur[v].y));
- insert(k, v + 2, pii(cur[v + 1].x, cur[v + 1].y - dy - ch));
- if (cur[v + 1].x > ovp1 && dy) {
- ++cur[v + 2].y; ++cur[v + 3].y;
- }
- normalize(k);
- } else {
- cord[i] = cur[v];
- nscale[i] = j;
- orient[i] = now;
- ax[i] = dx; ay[i] = dy;
- used[i] = 1;
- s += getS(i);
- used[i] = 0;
- rcord[i] = getCoord(i);
- int ovp1 = cur[v + 1].y;
- cur[v - 1] = pii(cur[v].x + dx + cw, cur[v].y + dy + ch);
- cur[v] = pii(cur[v].x + dx + cw, cur[v].y);
- if (dy && cur[v].x > ovp1) {
- ++cur[v].y; ++cur[v + 1].y;
- }
- normalize(k);
- }
- used[i] = 1;
- st[ssize++] = i;
- ms = min(ms, (scaled[i][j].x + dx) * (scaled[i][j].y + dy));
- rec(s, depth + 1);
- --ssize;
- k = old_k;
- memcpy(cur, old_cur, k * sizeof(pii));
- s = old_s;
- used[i] = 0;
- }
- // not found
- int shift = cur[v + 1].x - cur[v].x;
- if (v >= 2) shift = min(shift, cur[v - 2].x - cur[v - 1].x);
- if (shift * (cur[v - 1].y - cur[v].y) < ms) {
- cur[v].x += shift; cur[v - 1].x += shift;
- normalize(k);
- rec(s, depth + 1);
- }
- }
- void rec2(int s = 0, int depth = 0) {
- ++T;
- int bt = T;
- if (s > ans) {
- iter = 0;
- ans = s;
- bopt = opt;
- lastUpdate = getTime();
- rept(i, n) {
- if (used[i]) {
- best[i] = cord[i];
- bax[i] = ax[i];
- bay[i] = ay[i];
- borient[i] = orient[i];
- bnscale[i] = nscale[i];
- } else
- best[i] = pii(-1, -1);
- }
- }
- double currentTime = getTime();
- if (currentTime - startTime > 4.85) {
- out();
- }
- if (currentTime - startTime > TIME_LIMIT) {
- return;
- //out();
- }
- if (currentTime - lastUpdate > 0.05) {
- EX = 1;
- return;
- }
- ++iter;
- if (iter > 1000) return;
- if (k == 2) return;
- pii t = pii(INF, INF);
- int v = -1;
- rep(i, k - 2) {
- if (cur[i] < t) {
- t = cur[i];
- v = i;
- }
- }
- if (v == -1) return;
- if (cur[v].x >= w - 1 || cur[v].y >= h - 1) return;
- int can = s;
- int ry = 0;
- int sq = 0;
- rept(i, k - 1) {
- sq += cur[i].x * cur[i + 1].y - cur[i].y * cur[i + 1].x;
- if (!cur[i].x && !cur[i + 1].x) continue;
- if (!cur[i].y && !cur[i + 1].y) continue;
- if (cur[i].y == h && cur[i + 1].y == h) continue;
- }
- sq += 0 * cur[0].y - h * cur[0].x;
- if (sq < 0) sq = -sq;
- int per = 0, sum = 0;
- rept(i, n) {
- if (used[i]) continue;
- FORD(j, len[i] - 1, 0) {
- if (min(scaled[i][j].x, scaled[i][j].y) + cur[v].x > w) continue;
- if (scaled[i][j].x * scaled[i][j].y * 2 + sq > 2 * w * h) continue;
- per += scaled[i][j].x + scaled[i][j].y;
- ry = max(ry, min(scaled[i][j].x, scaled[i][j].y));
- break;
- }
- }
- int add = 2 * per - ry;
- can += add;
- if (can <= ans) return;
- int old_k = k, old_s = s;
- pair<pii, int> old_cur[204];
- memcpy(old_cur, cur, k * sizeof(pii));
- // insert
- int maxh = cur[v - 1].y - cur[v].y;
- int maxw = w - cur[v].x;
- int min_right = cur[v + 1].x - cur[v].x;
- if (v - 2 >= 0) min_right = min(min_right, cur[v - 2].x - cur[v - 1].x);
- int cnt = 0;
- vector<pair<pii, pii> > q;
- rept(i, n) {
- if (used[i]) continue;
- ++cnt;
- FORD(j, len[i] - 1, 0) {
- int cw = scaled[i][j].x, ch = scaled[i][j].y;
- int now = 1;
- rept(z, 2) {
- if (z == 1) {
- now = -now;
- swap(cw, ch);
- }
- if (cw > maxw || ch > maxh) continue;
- int dx = 0, dy = 0;
- int sx = 0, sy = 0;
- sumXY(cur[v].x, cur[v].y, cur[v].x + cw, cur[v].y + ch, sx, sy);
- if (sy * now > 0) dx = 1;
- if (sx * now > 0) dy = 1;
- if (cur[v].x + cw + dx > w || cur[v].y + ch + dy > h) continue;
- if (ch + dy < maxh) {
- cord[i] = cur[v];
- nscale[i] = j;
- orient[i] = now;
- ax[i] = dx; ay[i] = dy;
- used[i] = 1;
- int ns = s + getS(i);
- used[i] = 0;
- if (ns > s || !s) q.pb(mp(pii(ns, i), pii(j, (z << 2) | (dx << 1) | dy)));
- } else {
- cord[i] = cur[v];
- nscale[i] = j;
- orient[i] = now;
- ax[i] = dx; ay[i] = dy;
- used[i] = 1;
- int ns = s + getS(i);
- used[i] = 0;
- if (ns > s || !s) q.pb(mp(pii(ns, i), pii(j, (z << 2) | (dx << 1) | dy)));
- }
- s = old_s;
- }
- }
- }
- if (!cnt) return;
- if (!RN) {
- if (depth <= n / 2) DEP = 1; else
- DEP = 0;
- if (L(q) >= 2) partial_sort(q.begin(), q.begin() + 2, q.end(), cmp2);
- } else {
- sort(all(q)); reverse(all(q));
- int a = 0;
- while (a < L(q)) {
- int b = a;
- while (b < L(q) && q[a].x.x == q[b].x.x) ++b;
- random_shuffle(q.begin() + a, q.begin() + b);
- a = b;
- }
- }
- int ms = INF;
- rept(ii, L(q)) {
- if (ii == 1) break;
- int i = q[ii].x.y;
- int j = q[ii].y.x;
- int z = q[ii].y.y >> 2;
- if (used[i]) continue;
- int cw = scaled[i][j].x, ch = scaled[i][j].y;
- int now = 1;
- if (z == 1) {
- now = -now;
- swap(cw, ch);
- }
- if (cw > maxw || ch > maxh) continue;
- int dx = 0, dy = 0;
- dx = (q[ii].y.y >> 1) & 1;
- dy = (q[ii].y.y & 1);
- if (cur[v].x + cw + dx > w || cur[v].y + ch + dy > h) continue;
- if (ch + dy < maxh) {
- cord[i] = cur[v];
- nscale[i] = j;
- orient[i] = now;
- ax[i] = dx; ay[i] = dy;
- used[i] = 1;
- s += getS(i);
- used[i] = 0;
- rcord[i] = getCoord(i);
- int ovp1 = cur[v + 1].x;
- cur[v] = pii(cur[v].x, cur[v].y + dy + ch);
- insert(k, v + 1, pii(cur[v].x + dx + cw, cur[v].y));
- insert(k, v + 2, pii(cur[v + 1].x, cur[v + 1].y - dy - ch));
- if (cur[v + 1].x > ovp1 && dy) {
- ++cur[v + 2].y; ++cur[v + 3].y;
- }
- normalize(k);
- } else {
- cord[i] = cur[v];
- nscale[i] = j;
- orient[i] = now;
- ax[i] = dx; ay[i] = dy;
- used[i] = 1;
- s += getS(i);
- used[i] = 0;
- rcord[i] = getCoord(i);
- int ovp1 = cur[v + 1].y;
- cur[v - 1] = pii(cur[v].x + dx + cw, cur[v].y + dy + ch);
- cur[v] = pii(cur[v].x + dx + cw, cur[v].y);
- if (dy && cur[v].x > ovp1) {
- ++cur[v].y; ++cur[v + 1].y;
- }
- normalize(k);
- }
- used[i] = 1;
- st[ssize++] = i;
- ms = min(ms, scaled[i][j].x * scaled[i][j].y);
- rec2(s, depth + 1);
- --ssize;
- k = old_k;
- memcpy(cur, old_cur, k * sizeof(pii));
- s = old_s;
- used[i] = 0;
- }
- // not found
- int shift = cur[v + 1].x - cur[v].x;
- if (v >= 2) shift = min(shift, cur[v - 2].x - cur[v - 1].x);
- if (shift * (cur[v - 1].y - cur[v].y) < ms) {
- cur[v].x += shift; cur[v - 1].x += shift;
- normalize(k);
- rec2(s, depth + 1);
- }
- }
- int real_square[100001], rss;
- set<int> bil;
- map<int, int> replaced;
- int main() {
- srand(25091992);
- startTime = getTime();
- // freopen("input.txt","r",stdin);
- // freopen("output.txt","w",stdout);
- scanf("%d%d%d", &w, &h, &n); w *= 10; h *= 10;
- if (w > h) {
- SW = 1;
- swap(w, h);
- }
- rept(i, n) {
- scanf("%d%d", &a, &b);
- if (SW) swap(a, b);
- nomsq[i] = a * b;
- FOR(j, a, w) {
- if (j > 20 * a) break;
- if (b * j % a == 0) {
- scaled[i][len[i]++] = pii(j, b * j / a);
- }
- }
- }
- rept(i, n) {
- rept(j, len[i]) {
- real_square[rss++] = scaled[i][j].x * scaled[i][j].y;
- }
- }
- sort(real_square, real_square + rss);
- rss = unique(real_square, real_square + rss) - real_square;
- orient[101] = 2;
- lastUpdate = getTime();
- opt = w * h / n;
- int p1, p2, p3, s1, s2, s3;
- rept(hod, 3) {
- if (hod == 0 || hod == 1) {
- bil.clear();
- p1 = lower_bound(real_square, real_square + rss, w * h / (n + 1)) - real_square, s1 = 1;
- p2 = lower_bound(real_square, real_square + rss, w * h / n) - real_square, s2 = 1;
- p3 = lower_bound(real_square, real_square + rss, w * h / n * 4 / 3) - real_square, s3 = 1;
- }
- rept(i, 100000) {
- k = 0;
- cur[k++] = pii(0, h);
- cur[k++] = pii(0, 0);
- cur[k++] = pii(w, 0);
- if (i % 3 == 0) {
- opt = real_square[p1];
- p1 -= s1;
- p1 %= rss;
- if (p1 < 0) p1 += rss;
- if (opt < s1) {
- continue;
- }
- } else
- if (i % 3 == 1) {
- opt = real_square[p2];
- p2 += s2;
- p2 %= rss;
- if (opt > w * h + s2) continue;
- } else
- if (i % 3 == 2) {
- opt = real_square[p3];
- p3 += s3;
- p3 %= rss;
- if (opt > w * h + s3) continue;
- }
- int t = lower_bound(real_square, real_square + rss, opt) - real_square;
- if (bil.count(t)) {
- continue;
- }
- bil.insert(t);
- //if (hod == 1 && replaced.count(opt) && replaced[opt] < (double)ans * 0.5) continue;
- C(used); ssize = 0;
- lastStart = lastUpdate = getTime();
- updated_ans = 0;
- iter = 0;
- if (hod == 0) rec(); else
- if (hod == 1 || hod == 2) rec2();
- if (hod == 0) replaced[opt] = updated_ans;
- if (hod == 0 && getTime() - startTime > limit) break;
- if (hod == 1 && getTime() - startTime > TIME_LIMIT) break;
- }
- if (hod == 1) {
- int cnt = 0;
- rept(i, 30000) {
- int old = ans;
- //if (!nudge()) ++cnt;
- //if (getTime() - startTime > 4.85) break;
- //if (!nudge2()) ++cnt;
- if (!nudge3()) ++cnt;
- //if (cnt == 2) break;
- //if (ans != old) cerr << "WOW " << (double)ans / 10.0 << endl;
- if (getTime() - startTime > 4.85) break;
- //if (cnt == 4) break;
- }
- if (getTime() - startTime > 4.85) out();
- }
- }
- //wtf
- //cerr << "HERE" << endl;
- out();
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement