daily pastebin goal
12%
SHARE
TWEET

Challenge24 2014EC: Image Compression (author: Psyho)

a guest May 11th, 2015 213 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <bits/stdc++.h>
  2. #include <unistd.h>
  3. #include <sys/time.h>
  4. #include <thread>
  5.  
  6. #include <CImg.h>
  7. //#include <emmintrin.h>
  8.  
  9. using namespace std;
  10. using namespace cimg_library;
  11.  
  12. #define FORE(it,c)  for(__typeof((c).begin()) it = (c).begin(); it != (c).end(); ++it)
  13. #define FOR(i,a,b)  for(int i=(a);i<(b);++i)
  14. #define REP(i,a)    FOR(i,0,a)
  15. #define ZERO(m)    memset(m,0,sizeof(m))
  16. #define ALL(x)      x.begin(),x.end()
  17. #define PB          push_back
  18. #define S          size()
  19. #define LL          long long
  20. #define ULL        unsigned long long
  21. #define LD          long double
  22. #define MP          make_pair
  23. #define X          first
  24. #define Y          second
  25. #define VC          vector
  26. #define PII        pair <int, int>
  27. #define VI          VC < int >
  28. #define VPII          VC < PII >
  29. #define VVI        VC < VI >
  30. #define VD          VC < double >
  31. #define VVD        VC < VD >
  32. #define VS          VC < string >
  33. #define DB(a)      cerr << #a << ": " << (a) << endl;
  34.  
  35. template<class T> void print(VC < T > v) {cerr << "[";if (v.S) cerr << v[0];FOR(i, 1, v.S) cerr << ", " << v[i];cerr << "]\n";}
  36. template<class T> string i2s(T x) {ostringstream o; o << x; return o.str(); }
  37. VS splt(string s, char c = ' ') {VS all; int p = 0, np; while (np = s.find(c, p), np >= 0) {if (np != p) all.PB(s.substr(p, np - p)); p = np + 1;} if (p < s.S) all.PB(s.substr(p)); return all;}
  38.  
  39. int SX, SY;
  40. int bmp[1000][1000];
  41.  
  42. int px[2000];
  43. int py[2000];
  44. int pv[2000];
  45. int pno;
  46.  
  47. double calc() {
  48.         double rv = 0;
  49.         REP(x, SX) REP(y, SY) {
  50.                 double v = 0;
  51.                 double w = 0;
  52.                 REP(i, pno) {
  53.                         int d = (px[i] - x) * (px[i] - x) + (py[i] - y) * (py[i] - y);
  54.                         if (d == 0) {
  55.                                 v = pv[i];
  56.                                 w = 1;
  57.                                 break;
  58.                         }
  59.                         w += 1.0 / d;
  60.                         v += 1.0 / d * pv[i];
  61.                 }
  62.                 v /= w;
  63.                 rv += (v - bmp[x][y]) * (v - bmp[x][y]);
  64.         }
  65.         rv /= SX * SY;
  66.         rv = sqrt(rv);
  67.         return rv * 1000000;
  68. }
  69.  
  70. double tw[800][800];
  71. double tv[800][800];
  72. void tadd(int ox, int oy, int v) {
  73.         REP(x, SX) REP(y, SY) {
  74.                 int d = (ox - x) * (ox - x) + (oy - y) * (oy - y);
  75.                 double w = d == 0 ? 1e4 : 1.0 / d;
  76.                 tw[x][y] += w;
  77.                 tv[x][y] += w * v;
  78.         }
  79. }
  80.  
  81. void trem(int ox, int oy, int v) {
  82.         REP(x, SX) REP(y, SY) {
  83.                 int d = (ox - x) * (ox - x) + (oy - y) * (oy - y);
  84.                 double w = d == 0 ? 1e4 : 1.0 / d;
  85.                 tw[x][y] -= w;
  86.                 tv[x][y] -= w * v;
  87.         }
  88. }
  89.  
  90. double tcalc() {
  91.         double rv = 0;
  92.         REP(x, SX) REP(y, SY) {
  93.                 double a = tv[x][y] / tw[x][y];
  94.                 rv += (a - bmp[x][y]) * (a - bmp[x][y]);
  95.         }
  96.         return sqrt(rv / SX / SY) * 1e6;
  97.                
  98. }
  99.  
  100. void save(int test) {
  101.         char fout[100];
  102.         sprintf(fout, "J%d.out", test);
  103.         FILE *f = fopen(fout, "w");
  104.         fprintf(f, "%d\n", pno);
  105.         REP(i, pno) fprintf(f, "%d %d %d\n", px[i], py[i], pv[i]);
  106.         fclose(f);
  107. }
  108.  
  109. void hc(int test, int tries) {
  110.         const int dx[] = {-1,1,0,0,-1,-1,1,1,0,0};
  111.         const int dy[] = {0,0,-1,1,-1,1,-1,1,0,0};
  112.        
  113.         REP(i, pno) tadd(px[i], py[i], pv[i]);
  114.         double bv = tcalc();
  115.        
  116.         int lastImp = -10000;
  117.        
  118.         REP(cur, tries) {
  119.                 int p = rand() % pno;
  120.                 int t = rand() % 2;
  121.                 int d = rand() % 10;
  122.                 int v = 3 - rand() % 7;
  123.                
  124.                 if (v == 0 && d >= 8) continue;
  125.                
  126.                 int ox = px[p];
  127.                 int oy = py[p];
  128.                 int ov = pv[p];
  129.                 int nx = px[p] + dx[d];
  130.                 int ny = py[p] + dy[d];
  131.                 if (nx < 0 || nx >= SX || ny < 0 || ny >= SY) continue;
  132.                 int ok = 0;
  133.                 REP(i, pno) ok += px[i] == nx && py[i] == ny;
  134.                 if (ok) continue;
  135.                 int nv = pv[p] + v;
  136.                 if (nv < 0 || nv >= 256) continue;
  137.                 trem(px[p], py[p], pv[p]);
  138.                 px[p] = nx;
  139.                 py[p] = ny;
  140.                 pv[p] = nv;
  141.                 tadd(px[p], py[p], pv[p]);
  142.                
  143.                 double av = tcalc();
  144.                 if (av < bv) {
  145.                         if (cur > lastImp + 5000) {
  146.                                 cerr << cur << ' ' << av << ' ' << calc() << endl;
  147.                                 save(test);
  148.                                 lastImp = cur;
  149.                         }
  150.                        
  151.                         bv = av;
  152.                 } else {
  153.                         trem(px[p], py[p], pv[p]);
  154.                         px[p] = ox;
  155.                         py[p] = oy;
  156.                         pv[p] = ov;
  157.                         tadd(px[p], py[p], pv[p]);
  158.                 }
  159.         }
  160.        
  161.         DB(calc());
  162. }
  163.  
  164. void load(int test) {
  165.         string fimg = i2s(test) + ".bmp";
  166.         CImg<unsigned char> img(fimg.c_str());
  167.         SX = img.width();
  168.         SY = img.height();
  169.         REP(x, img.width()) REP(y, img.height()) bmp[x][y] = img(x, y);
  170. }
  171.  
  172. void run(int test, int tries = 0) {
  173.         load(test);
  174.        
  175.        
  176.         int bx = 0, by = 0;
  177.         FOR(sx, 1, SX) FOR(sy, 1, SY) {
  178.                 if (sx * sy <= SX + SY && ((sx * sy >= bx * by - 10 && min(sx, sy) > min(bx, by)) || sx * sy >= bx * by && min(sx, sy) >= min(bx, by))) bx = sx, by = sy;
  179.         }
  180.        
  181.         pno = 0;
  182.         ZERO(px);
  183.         ZERO(py);
  184.         ZERO(pv);
  185.         REP(x, bx) REP(y, by) {
  186.                 px[pno] = (int)((x + 0.5) * SX / bx + 0.5);
  187.                 py[pno] = (int)((y + 0.5) * SY / by + 0.5);
  188.                 int no = 0;
  189.                 FOR(i, -2, 3) FOR(j, -2, 3) pv[pno] += bmp[px[pno]+i][py[pno]+j], no++;
  190.                 pv[pno] = (pv[pno] + no / 2) / no;
  191.                 pno++;
  192.         }
  193.        
  194.         while (pno < SX + SY) {
  195.                 px[pno] = rand() % SX;
  196.                 py[pno] = rand() % SY;
  197.                 pv[pno] = bmp[px[pno]][py[pno]];
  198.                 pno++;
  199.         }
  200.        
  201.         DB(calc());
  202.        
  203.         save(test);
  204.        
  205.         if (tries) hc(test, tries);
  206.        
  207. }
  208.  
  209. void loadSolution(string fn) {
  210.         fstream fs(fn.c_str());
  211.         fs >> pno;
  212.         REP(i, pno) fs >> px[i] >> py[i] >> pv[i];
  213.         fs.close();
  214. }
  215.  
  216. int main(int argc, char **argv) {
  217.         int t = atoi(argv[1]);
  218.         if (!isdigit(argv[2][0])) {
  219.                 load(t);
  220.                 DB(1);
  221.                 loadSolution(argv[2]);
  222.                 DB(2);
  223.                 DB(calc());
  224.         } else {
  225.                 run(t, atoi(argv[2]));
  226.         }
  227. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top