Set trong C++

Tổng quan

  • Set là một loại associative containers để lưu trữ các phần tử không bị trùng lặp (unique elements), và các phần tử này chính là các khóa (keys).
  • Khi duyệt set theo iterator từ begin đến end, các phần tử của set sẽ tăng dần theo phép toán so sánh.
  • Mặc định của set là sử dụng phép toán less, bạn cũng có thể viết lại hàm so sánh theo ý mình.
  • Set được thực hiện giống như cây tìm kiếm nhị phân (Binary search tree).

Khai báo:

#include 
set  s;
set  > s;

Hoặc viết class so sánh theo ý mình:

struct cmp{
bool operator() (int a,int b) {return a myset ;

Capacity:

  • size : trả về kích thước hiện tại của set. ĐPT O(1)
  • empty : true nếu set rỗng, và ngược lại. ĐPT O(1).

Thay đổi:

  • insert : Chèn phần tử vào set. ĐPT O(logN).
  • erase : có 2 kiểu xóa: xóa theo iterator, hoặc là xóa theo khóa. ĐPT O(logN).
  • clear : xóa tất cả set. ĐPT O(n).
  • swap : đổi 2 set cho nhau. ĐPT O(n).

Truy cập phần tử:

  • find : trả về itarator trỏ đến phần tử cần tìm kiếm. Nếu không tìm thấy itarator trỏ về “end” của set. ĐPT O(logN).
  • lower_bound : trả về iterator đến vị trí phần tử bé nhất mà không bé hơn (lớn hơn hoặc bằng) khóa (dĩ nhiên là theo phép so sánh), nếu không tìm thấy trả về vị trí “end” của set. ĐPT O(logN).
  • upper_bound: trả về iterator đến vị trí phần tử bé nhất mà lớn hơn khóa, nếu không tìm thấy trả về vị trí “end” của set.. ĐPT O(logN).
  • count : trả về số lần xuất hiện của khóa trong container. Nhưng trong set, các phần tử chỉ xuất hiện một lần, nên hàm này có ý nghĩa là sẽ return 1 nếu khóa có trong container, và 0 nếu không có. ĐPT O(logN).

 

Chương trình Demo 1:

#include 
#include 
using namespace std;
main() {
      set  s;
      set  ::iterator it; s.insert(9);	// s={9}
      s.insert(5);	// s={5,9} cout << *s.begin() << endl; //In ra 5 s.insert(1);	// s={1,5,9} cout << *s.begin() << endl; // In ra 1

      it=s.find(5);
      if (it==s.end()) cout << "Khong co trong container" << endl; else  cout << "Co trong container" << endl;

      s.erase(it);	// s={1,9}
      s.erase(1);	// s={9}

      s.insert(3);	// s={3,9}
      s.insert(4);	// s={3,4,9}

      it=s.lower_bound(4);
      if (it==s.end()) cout << "Khong co phan tu nao trong set khong be hon 4" << endl; else cout << "Phan tu be nhat khong be hon 4 la " << *it << endl;  // In ra 4

      it=s.lower_bound(10);
      if (it==s.end()) cout << "Khong co phan tu nao trong set khong be hon 10" << endl; else cout << "Phan tu be nhat khong be hon 10 la " << *it << endl; // Khong co ptu nao

      it=s.upper_bound(4);
      if (it==s.end()) cout << "Khong co phan tu nao trong set lon hon 4" << endl; else cout << "Phan tu be nhat lon hon 4 la " << *it << endl;	// In ra 9

      /* Duyet set */

      for (it=s.begin();it!=s.end();it++) { cout << *it <<  " ";
      }
      // In ra 3 4 9

      cout << endl; system("pause");
}

Lưu ý: Nếu bạn muốn sử dụng hàm lower_bound hay upper_bound để tìm phần tử lớn nhất “bé hơn hoặc bằng” hoặc “bé hơn” bạn có thể thay đổi cách so sánh của set để tìm kiếm. Mời bạn xem chương trình sau để rõ hơn:

#include 
#include 
#include  using namespace std;
main() {
      set  > s;
      set  > :: iterator it; // Phép toán so sánh là greater

      s.insert(1);	// s={1}
      s.insert(2);	// s={2,1}
      s.insert(4);	// s={4,2,1}
      s.insert(9);	// s={9,4,2,1}

      /* Tim phần tử lớn nhất bé hơn hoặc bằng 5 */ it=s.lower_bound(5);
      cout << *it << endl;	// In ra 4

      /* Tim phần tử lớn nhất bé hơn 4 */ it=s.upper_bound(4);
      cout << *it << endl;	// In ra 2

      system("pause");
}

QBHEAP – spoj

Đề bài:

Thuật toán:

  • Với C++ bạn có thể dùng sẵn CTDL Priority Queue (hàng đợi ưu tiên). Còn với Pascal thì bạn phải tự viết CTDL Heap

Code:

#include 

using namespace std;

const int MAXN = 20000;
string s;
priority_queue  h;
char key;
int num, a[MAXN];

bool cmp(int a, int b) {
    return (a > b);
}

int main() {
    //freopen("test.inp","r",stdin);
    //freopen("test.out","w",stdout);
    // solve
    getline(cin, s);
    do {
        key = s[0];
        if (key == '+') {
            s.erase(0,1);
            num = atoi(s.c_str());
            if (h.size()<15000) h.push(num);
        } else if (!h.empty())
        {
            num = h.top();
            while (!h.empty() && h.top()==num) h.pop();
        }
        getline(cin, s);
    } while (s != "");
    // pop
    int res = 0;
    while (!h.empty()) {
        res++;
        a[res] = h.top();
        while (!h.empty() && h.top()==a[res]) h.pop();
    }
    // print
    cout << res << endl;
    for (int i = 1; i <= res; i++) cout << a[i] << endl;
    return 0;
}
const   fi='';
        fo='';
        maxn=15000+3;
var     h:array[1..maxn] of longint;
        i,j:longint;
        res:array[0..maxn] of longint;
        nh,n,ans:longint;
procedure swap(var x,y:longint);
var     tg:longint;
begin
        tg:=x;x:=y;y:=tg;
end;
procedure qs(l,r:longint);
var     x,i,j:longint;
begin
            i:=l;j:=r;
            x:=res[(i+j) div 2];
            repeat
                while res[i]>x do inc(i);
                while res[j]j;
            if il then qs(l,j);
end;
procedure downheap(i:longint);
var     j:longint;
begin
        j:= i + i;
        if j>nh then exit;
        if (jh[i] then
                begin
                        swap(h[i],h[j]);
                        downheap(j);
                end;
end;
procedure upheap(i:longint);
var     j:longint;
begin
        j:=i div 2;
        if i>1 then
        if h[i]>h[j] then
                begin
                        swap(h[i],h[j]);
                        upheap(j);
                end;
end;
procedure push(x:longint);
begin
        inc(nh);
        h[nh]:=x;
        upheap(nh);
end;
function pop:longint;
begin
        pop:=h[1];
        h[1]:=h[nh];
        dec(nh);
        downheap(1);
end;
procedure xuat;
begin
        for i:=1 to n do
                if res[i]<>res[i-1] then writeln(res[i]);
end;
procedure main;
var     tam,s:string;
        x,err:longint;
begin
    assign(input,fi);reset(input);
    assign(output,fo);rewrite(output);

    while not seekeof(input) do
        begin
            readln(s);
            if s[1]='+' then
            begin
              if nh<15000 then
                begin
                    tam:=copy(s,2,length(s));
                    val(tam,x,err);
                    push(x);
                end
                end
                ELSE
                if nh>0 then
                begin
                        if nh>0 then x:=pop;
                        while (nh>0) and (h[1]=x) do pop;
                end;
        end;
        for i:=1 to nh do
                begin
                        res[i]:=pop;
                        inc(n);
                end;
        qs(1,n);
        res[0]:=-1;
        for i:=1 to n do
                if res[i]<>res[i-1] then inc(ans);
        writeln(ans);
        xuat;

    close(input);close(output);
end;
begin
    main;
end.

[Android] Chèn ảnh động *.gif trong Android

Tạo một ứng dụng Android và đặt tên là AnimationGif với Activity chính là MainActivity.
Tiếp theo, ta copy một hình ảnh có định dạng *.gif vào trong thư mục /assets. Ở đây mình sẽ sử dụng tập tin test.gif.

Cách 1: Sử dụng GifDecoderView

Để hiển thị được ảnh dạng *.gif, chúng ta sẽ sử dụng một custom view có tên là GifDecoderView, và cần một class để decode tập tin *.gif, có tên là GifDecoder.


GifDecoder.java

public class GifDecoder {
        /**
         * File read status: No errors.
         */
        public static final int STATUS_OK = 0;
        /**
         * File read status: Error decoding file (may be partially decoded)
         */
        public static final int STATUS_FORMAT_ERROR = 1;
        /**
         * File read status: Unable to open source.
         */
        public static final int STATUS_OPEN_ERROR = 2;
        /** max decoder pixel stack size */
        protected static final int MAX_STACK_SIZE = 4096;
        protected InputStream in;
        protected int status;
        protected int width; // full image width
        protected int height; // full image height
        protected boolean gctFlag; // global color table used
        protected int gctSize; // size of global color table
        protected int loopCount = 1; // iterations; 0 = repeat forever
        protected int[] gct; // global color table
        protected int[] lct; // local color table
        protected int[] act; // active color table
        protected int bgIndex; // background color index
        protected int bgColor; // background color
        protected int lastBgColor; // previous bg color
        protected int pixelAspect; // pixel aspect ratio
        protected boolean lctFlag; // local color table flag
        protected boolean interlace; // interlace flag
        protected int lctSize; // local color table size
        protected int ix, iy, iw, ih; // current image rectangle
        protected int lrx, lry, lrw, lrh;
        protected Bitmap image; // current frame
        protected Bitmap lastBitmap; // previous frame
        protected byte[] block = new byte[256]; // current data block
        protected int blockSize = 0; // block size last graphic control extension info
        protected int dispose = 0; // 0=no action; 1=leave in place; 2=restore to bg; 3=restore to prev
        protected int lastDispose = 0;
        protected boolean transparency = false; // use transparent color
        protected int delay = 0; // delay in milliseconds
        protected int transIndex; // transparent color index
        // LZW decoder working arrays
        protected short[] prefix;
        protected byte[] suffix;
        protected byte[] pixelStack;
        protected byte[] pixels;
        protected Vector frames; // frames read from current file
        protected int frameCount;

        private static class GifFrame {
                public GifFrame(Bitmap im, int del) {
                        image = im;
                        delay = del;
                }

                public Bitmap image;
                public int delay;
        }

        /**
         * Gets display duration for specified frame.
         *
         * @param n
         *          int index of frame
         * @return delay in milliseconds
         */
        public int getDelay(int n) {
                delay = -1;
                if ((n >= 0) && (n < frameCount)) {
                        delay = frames.elementAt(n).delay;
                }
                return delay;
        }

        /**
         * Gets the number of frames read from file.
         *
         * @return frame count
         */
        public int getFrameCount() {
                return frameCount;
        }

        /**
         * Gets the first (or only) image read.
         *
         * @return BufferedBitmap containing first frame, or null if none.
         */
        public Bitmap getBitmap() {
                return getFrame(0);
        }

        /**
         * Gets the "Netscape" iteration count, if any. A count of 0 means repeat indefinitiely.
         *
         * @return iteration count if one was specified, else 1.
         */
        public int getLoopCount() {
                return loopCount;
        }

        /**
         * Creates new frame image from current data (and previous frames as specified by their disposition codes).
         */
        protected void setPixels() {
                // expose destination image's pixels as int array
                int[] dest = new int[width * height];
                // fill in starting image contents based on last image's dispose code
                if (lastDispose > 0) {
                        if (lastDispose == 3) {
                                // use image before last
                                int n = frameCount - 2;
                                if (n > 0) {
                                        lastBitmap = getFrame(n - 1);
                                } else {
                                        lastBitmap = null;
                                }
                        }
                        if (lastBitmap != null) {
                                lastBitmap.getPixels(dest, 0, width, 0, 0, width, height);
                                // copy pixels
                                if (lastDispose == 2) {
                                        // fill last image rect area with background color
                                        int c = 0;
                                        if (!transparency) {
                                                c = lastBgColor;
                                        }
                                        for (int i = 0; i < lrh; i++) {
                                                int n1 = (lry + i) * width + lrx;
                                                int n2 = n1 + lrw;
                                                for (int k = n1; k < n2; k++) {
                                                        dest[k] = c;
                                                }
                                        }
                                }
                        }
                }
                // copy each source line to the appropriate place in the destination
                int pass = 1;
                int inc = 8;
                int iline = 0;
                for (int i = 0; i < ih; i++) {
                        int line = i;
                        if (interlace) {
                                if (iline >= ih) {
                                        pass++;
                                        switch (pass) {
                                        case 2:
                                                iline = 4;
                                                break;
                                        case 3:
                                                iline = 2;
                                                inc = 4;
                                                break;
                                        case 4:
                                                iline = 1;
                                                inc = 2;
                                                break;
                                        default:
                                                break;
                                        }
                                }
                                line = iline;
                                iline += inc;
                        }
                        line += iy;
                        if (line < height) {
                                int k = line * width;
                                int dx = k + ix; // start of line in dest
                                int dlim = dx + iw; // end of dest line
                                if ((k + width) < dlim) {
                                        dlim = k + width; // past dest edge
                                }
                                int sx = i * iw; // start of line in source
                                while (dx < dlim) {
                                        // map color and insert in destination
                                        int index = ((int) pixels[sx++]) & 0xff;
                                        int c = act[index];
                                        if (c != 0) {
                                                dest[dx] = c;
                                        }
                                        dx++;
                                }
                        }
                }
                image = Bitmap.createBitmap(dest, width, height, Config.ARGB_4444);
        }

        /**
         * Gets the image contents of frame n.
         *
         * @return BufferedBitmap representation of frame, or null if n is invalid.
         */
        public Bitmap getFrame(int n) {
                if (frameCount <= 0)
                        return null;
                n = n % frameCount;
                return ((GifFrame) frames.elementAt(n)).image;
        }

        /**
         * Reads GIF image from stream
         *
         * @param is
         *          containing GIF file.
         * @return read status code (0 = no errors)
         */
        public int read(InputStream is) {
                init();
                if (is != null) {
                        in = is;
                        readHeader();
                        if (!err()) {
                                readContents();
                                if (frameCount < 0) {
                                        status = STATUS_FORMAT_ERROR;
                                }
                        }
                } else {
                        status = STATUS_OPEN_ERROR;
                }
                try {
                        is.close();
                } catch (Exception e) {
                }
                return status;
        }

        /**
         * Decodes LZW image data into pixel array. Adapted from John Cristy's BitmapMagick.
         */
        protected void decodeBitmapData() {
                int nullCode = -1;
                int npix = iw * ih;
                int available, clear, code_mask, code_size, end_of_information, in_code, old_code, bits, code, count, i, datum, data_size, first, top, bi, pi;
                if ((pixels == null) || (pixels.length < npix)) {
                        pixels = new byte[npix]; // allocate new pixel array
                }
                if (prefix == null) {
                        prefix = new short[MAX_STACK_SIZE];
                }
                if (suffix == null) {
                        suffix = new byte[MAX_STACK_SIZE];
                }
                if (pixelStack == null) {
                        pixelStack = new byte[MAX_STACK_SIZE + 1];
                }
                // Initialize GIF data stream decoder.
                data_size = read();
                clear = 1 << data_size;
                end_of_information = clear + 1;
                available = clear + 2;
                old_code = nullCode;
                code_size = data_size + 1;
                code_mask = (1 << code_size) - 1;
                for (code = 0; code < clear; code++) {
                        prefix[code] = 0;
                        suffix[code] = (byte) code;
                }
                // Decode GIF pixel stream.
                datum = bits = count = first = top = pi = bi = 0;
                for (i = 0; i < npix;) {
                        if (top == 0) {
                                if (bits < code_size) {
                                        // Load bytes until there are enough bits for a code.
                                        if (count == 0) {
                                                // Read a new data block.
                                                count = readBlock();
                                                if (count <= 0) {
                                                        break;
                                                }
                                                bi = 0;
                                        }
                                        datum += (((int) block[bi]) & 0xff) << bits;
                                        bits += 8;
                                        bi++;
                                        count--;
                                        continue;
                                }
                                // Get the next code.
                                code = datum & code_mask;
                                datum >>= code_size;
                                bits -= code_size;
                                // Interpret the code
                                if ((code > available) || (code == end_of_information)) {
                                        break;
                                }
                                if (code == clear) {
                                        // Reset decoder.
                                        code_size = data_size + 1;
                                        code_mask = (1 << code_size) - 1;
                                        available = clear + 2;
                                        old_code = nullCode;
                                        continue;
                                }
                                if (old_code == nullCode) {
                                        pixelStack[top++] = suffix[code];
                                        old_code = code;
                                        first = code;
                                        continue;
                                }
                                in_code = code;
                                if (code == available) {
                                        pixelStack[top++] = (byte) first;
                                        code = old_code;
                                }
                                while (code > clear) {
                                        pixelStack[top++] = suffix[code];
                                        code = prefix[code];
                                }
                                first = ((int) suffix[code]) & 0xff;
                                // Add a new string to the string table,
                                if (available >= MAX_STACK_SIZE) {
                                        break;
                                }
                                pixelStack[top++] = (byte) first;
                                prefix[available] = (short) old_code;
                                suffix[available] = (byte) first;
                                available++;
                                if (((available & code_mask) == 0) && (available < MAX_STACK_SIZE)) {
                                        code_size++;
                                        code_mask += available;
                                }
                                old_code = in_code;
                        }
                        // Pop a pixel off the pixel stack.
                        top--;
                        pixels[pi++] = pixelStack[top];
                        i++;
                }
                for (i = pi; i < npix; i++) {
                        pixels[i] = 0; // clear missing pixels
                }
        }

        /**
         * Returns true if an error was encountered during reading/decoding
         */
        protected boolean err() {
                return status != STATUS_OK;
        }

        /**
         * Initializes or re-initializes reader
         */
        protected void init() {
                status = STATUS_OK;
                frameCount = 0;
                frames = new Vector();
                gct = null;
                lct = null;
        }

        /**
         * Reads a single byte from the input stream.
         */
        protected int read() {
                int curByte = 0;
                try {
                        curByte = in.read();
                } catch (Exception e) {
                        status = STATUS_FORMAT_ERROR;
                }
                return curByte;
        }

        /**
         * Reads next variable length block from input.
         *
         * @return number of bytes stored in "buffer"
         */
        protected int readBlock() {
                blockSize = read();
                int n = 0;
                if (blockSize > 0) {
                        try {
                                int count = 0;
                                while (n < blockSize) {
                                        count = in.read(block, n, blockSize - n);
                                        if (count == -1) {
                                                break;
                                        }
                                        n += count;
                                }
                        } catch (Exception e) {
                                e.printStackTrace();
                        }
                        if (n < blockSize) {
                                status = STATUS_FORMAT_ERROR;
                        }
                }
                return n;
        }

        /**
         * Reads color table as 256 RGB integer values
         *
         * @param ncolors
         *          int number of colors to read
         * @return int array containing 256 colors (packed ARGB with full alpha)
         */
        protected int[] readColorTable(int ncolors) {
                int nbytes = 3 * ncolors;
                int[] tab = null;
                byte[] c = new byte[nbytes];
                int n = 0;
                try {
                        n = in.read(c);
                } catch (Exception e) {
                        e.printStackTrace();
                }
                if (n < nbytes) {
                        status = STATUS_FORMAT_ERROR;
                } else {
                        tab = new int[256]; // max size to avoid bounds checks
                        int i = 0;
                        int j = 0;
                        while (i < ncolors) {
                                int r = ((int) c[j++]) & 0xff;
                                int g = ((int) c[j++]) & 0xff;
                                int b = ((int) c[j++]) & 0xff;
                                tab[i++] = 0xff000000 | (r << 16) | (g << 8) | b;
                        }
                }
                return tab;
        }

        /**
         * Main file parser. Reads GIF content blocks.
         */
        protected void readContents() {
                // read GIF file content blocks
                boolean done = false;
                while (!(done || err())) {
                        int code = read();
                        switch (code) {
                        case 0x2C: // image separator
                                readBitmap();
                                break;
                        case 0x21: // extension
                                code = read();
                                switch (code) {
                                case 0xf9: // graphics control extension
                                        readGraphicControlExt();
                                        break;
                                case 0xff: // application extension
                                        readBlock();
                                        String app = "";
                                        for (int i = 0; i < 11; i++) {
                                                app += (char) block[i];
                                        }
                                        if (app.equals("NETSCAPE2.0")) {
                                                readNetscapeExt();
                                        } else {
                                                skip(); // don't care
                                        }
                                        break;
                                case 0xfe:// comment extension
                                        skip();
                                        break;
                                case 0x01:// plain text extension
                                        skip();
                                        break;
                                default: // uninteresting extension
                                        skip();
                                }
                                break;
                        case 0x3b: // terminator
                                done = true;
                                break;
                        case 0x00: // bad byte, but keep going and see what happens break;
                        default:
                                status = STATUS_FORMAT_ERROR;
                        }
                }
        }

        /**
         * Reads Graphics Control Extension values
         */
        protected void readGraphicControlExt() {
                read(); // block size
                int packed = read(); // packed fields
                dispose = (packed & 0x1c) >> 2; // disposal method
                if (dispose == 0) {
                        dispose = 1; // elect to keep old image if discretionary
                }
                transparency = (packed & 1) != 0;
                delay = readShort() * 10; // delay in milliseconds
                transIndex = read(); // transparent color index
                read(); // block terminator
        }

        /**
         * Reads GIF file header information.
         */
        protected void readHeader() {
                String id = "";
                for (int i = 0; i < 6; i++) {
                        id += (char) read();
                }
                if (!id.startsWith("GIF")) {
                        status = STATUS_FORMAT_ERROR;
                        return;
                }
                readLSD();
                if (gctFlag && !err()) {
                        gct = readColorTable(gctSize);
                        bgColor = gct[bgIndex];
                }
        }

        /**
         * Reads next frame image
         */
        protected void readBitmap() {
                ix = readShort(); // (sub)image position & size
                iy = readShort();
                iw = readShort();
                ih = readShort();
                int packed = read();
                lctFlag = (packed & 0x80) != 0; // 1 - local color table flag interlace
                lctSize = (int) Math.pow(2, (packed & 0x07) + 1);
                // 3 - sort flag
                // 4-5 - reserved lctSize = 2 << (packed & 7); // 6-8 - local color
                // table size
                interlace = (packed & 0x40) != 0;
                if (lctFlag) {
                        lct = readColorTable(lctSize); // read table
                        act = lct; // make local table active
                } else {
                        act = gct; // make global table active
                        if (bgIndex == transIndex) {
                                bgColor = 0;
                        }
                }
                int save = 0;
                if (transparency) {
                        save = act[transIndex];
                        act[transIndex] = 0; // set transparent color if specified
                }
                if (act == null) {
                        status = STATUS_FORMAT_ERROR; // no color table defined
                }
                if (err()) {
                        return;
                }
                decodeBitmapData(); // decode pixel data
                skip();
                if (err()) {
                        return;
                }
                frameCount++;
                // create new image to receive frame data
                image = Bitmap.createBitmap(width, height, Config.ARGB_4444);
                setPixels(); // transfer pixel data to image
                frames.addElement(new GifFrame(image, delay)); // add image to frame
                // list
                if (transparency) {
                        act[transIndex] = save;
                }
                resetFrame();
        }

        /**
         * Reads Logical Screen Descriptor
         */
        protected void readLSD() {
                // logical screen size
                width = readShort();
                height = readShort();
                // packed fields
                int packed = read();
                gctFlag = (packed & 0x80) != 0; // 1 : global color table flag
                // 2-4 : color resolution
                // 5 : gct sort flag
                gctSize = 2 << (packed & 7); // 6-8 : gct size
                bgIndex = read(); // background color index
                pixelAspect = read(); // pixel aspect ratio
        }

        /**
         * Reads Netscape extenstion to obtain iteration count
         */
        protected void readNetscapeExt() {
                do {
                        readBlock();
                        if (block[0] == 1) {
                                // loop count sub-block
                                int b1 = ((int) block[1]) & 0xff;
                                int b2 = ((int) block[2]) & 0xff;
                                loopCount = (b2 << 8) | b1;
                        }
                } while ((blockSize > 0) && !err());
        }

        /**
         * Reads next 16-bit value, LSB first
         */
        protected int readShort() {
                // read 16-bit value, LSB first
                return read() | (read() << 8);
        }

        /**
         * Resets frame state for reading next image.
         */
        protected void resetFrame() {
                lastDispose = dispose;
                lrx = ix;
                lry = iy;
                lrw = iw;
                lrh = ih;
                lastBitmap = image;
                lastBgColor = bgColor;
                dispose = 0;
                transparency = false;
                delay = 0;
                lct = null;
        }

        /**
         * Skips variable length blocks up to and including next zero length block.
         */
        protected void skip() {
                do {
                        readBlock();
                } while ((blockSize > 0) && !err());
        }
}

GifDecoderView.java

public class GifDecoderView extends ImageView {

	public GifDecoderView(Context context) {
		super(context);
	}

	public GifDecoderView(Context context, InputStream stream) {
		super(context);
		playGif(stream);
	}

	private boolean mIsPlayingGif = false;

	private GifDecoder mGifDecoder;

	private Bitmap mTmpBitmap;

	final Handler mHandler = new Handler();

	final Runnable mUpdateResults = new Runnable() {
		public void run() {
			if (mTmpBitmap != null && !mTmpBitmap.isRecycled()) {
				GifDecoderView.this.setImageBitmap(mTmpBitmap);
			}
		}
	};

	private void playGif(InputStream stream) {
		mGifDecoder = new GifDecoder();
		mGifDecoder.read(stream);

		mIsPlayingGif = true;

		new Thread(new Runnable() {
			public void run() {
				final int n = mGifDecoder.getFrameCount();
				final int ntimes = mGifDecoder.getLoopCount();
				int repetitionCounter = 0;
				do {
					for (int i = 0; i < n; i++) {
						mTmpBitmap = mGifDecoder.getFrame(i);
						int t = mGifDecoder.getDelay(i);
						mHandler.post(mUpdateResults);
						try {
							Thread.sleep(t);
						} catch (InterruptedException e) {
							e.printStackTrace();
						}
					}
					if (ntimes != 0) {
						repetitionCounter++;
					}
				} while (mIsPlayingGif && (repetitionCounter <= ntimes));
			}
		}).start();
	}

	public void stopRendering() {
		mIsPlayingGif = true;
	}
}

Tiếp theo, ta chỉnh sửa MainActivity để hiển thị tập tin test.gif.
Chúng ta đọc tập tin test.gif vào trong một InputStream

		InputStream stream = null;
		try {
			stream = getAssets().open("test.gif");
		} catch (IOException e) {
			e.printStackTrace();
		}

Sau đó khởi tạo một GifDecoderView với tham số là InputStream vừa có như sau

		GifDecoderView view = new GifDecoderView(this, stream);

Cuối cùng là gán nội dung vào view của Activity để hiển thị:

		setContentView(view);

Cách 2: Sử dụng GifWebView

Cách này, chúng ta sẽ sử dụng GifWebView. Thực tế, ở đây ta sử dụng WebView, chỉ là custom lại để hiển thị ảnh từ đường dẫn đưa vào.
Tạo một class GifWebView với nội dung sau.

public class GifWebView extends WebView {

	public GifWebView(Context context, String path) {
		super(context);
		loadUrl(path);
	}
}

Sau đó, chỉnh sửa lại MainActivity. Chúng ta chỉ cần một đoạn mã sau để hiển thị test.gif

		GifWebView view = new GifWebView(this,"file:///android_asset/test.gif");

Và gán view này để hiển thị trên thiết bị:

		setContentView(view);

QBPOINT – SPOJ

Đề bài: http://vn.spoj.com/problems/QBPOINT/

Thuật toán:

  • Duyệt n điểm, với mỗi điểm i ta:
    • Duyệt các điểm j <> i rồi tính vector ij lưu lại vào 1 mảng ss[]
    • Sort lại mảng ss[]
    • 3 điểm i,j,k thẳng hàng nếu vector ij = vector ik

Code:

#include 
#define FORE(i, a, b) for(int i = a; i <= b; i++)
#define FORD(i, a, b) for(int i = a; i >= b; i--)
#define FOR(i, a, b) for(int i = a; i < b; i++)
const int MAXN = 1e5 * 5;
const int INF = 1e9 + 7;

using namespace std;
int n,x[2001],y[2001];
long long res;
int main()
{
    ios::sync_with_stdio(0); cin.tie(0);
    #ifndef ONLINE_JUDGE
    freopen("tripoint.inp", "r", stdin);
    freopen("tripoint.out", "w", stdout);
    #endif //
    cin>>n;
    FORE(i,1,n) cin>>x[i]>>y[i];
    FORE(i,1,n)
    {
        vector  ss; int cc=0;
        FORE(j,1,n)
        if (x[j]!=x[i])
            ss.push_back((double) (y[j]-y[i])/(x[j]-x[i]));
        else ++cc;
        sort(ss.begin(),ss.end());
        int sl=(cc-2)*(cc-1);
        if (ss.size())
        {
            int dem=1;
            FORE(j,1,ss.size()-1)
            if (ss[j]==ss[j-1]) ++dem;
            else
            {
                sl+=dem*(dem-1);
                dem=1;
            }
            sl+=dem*(dem-1);
        }
        res+=sl;
    }
    cout<