轉(zhuǎn)自：http://blog.sina.com.cn/s/blog_4d035b080100k3ep.html?retcode=0
opengl文字處理（1） （入門學(xué)習(xí)十六）（轉(zhuǎn)）

OpenGL版的“Hello, World!”
寫完了本課，我的感受是：顯示文字很簡(jiǎn)單，顯示文字很復(fù)雜。看似簡(jiǎn)單的功能，背后卻隱藏了深不可測(cè)的玄機(jī)。
呵呵，別一開(kāi)始就被嚇住了，讓我們先從“Hello, World!”開(kāi)始。
前面已經(jīng)說(shuō)過(guò)了，要顯示字符，就需要通過(guò)操作系統(tǒng)，把繪制字符的動(dòng)作裝到顯示列表中，然后我們調(diào)用顯示列表即可繪制字符。
假如我們要顯示的文字全部是ASCII字符，則總共只有0到127這128種可能，因此可以預(yù)先把所有的字符分別裝到對(duì)應(yīng)的顯示列表中，然后在需要時(shí)調(diào)用這些顯示列表。
Windows系統(tǒng)中，可以使用wglUseFontBitmaps函數(shù)來(lái)批量的產(chǎn)生顯示字符用的顯示列表。函數(shù)有四個(gè)參數(shù)：
第一個(gè)參數(shù)是HDC，學(xué)過(guò)Windows GDI的朋友應(yīng)該會(huì)熟悉這個(gè)。如果沒(méi)有學(xué)過(guò)，那也沒(méi)關(guān)系，只要知道調(diào)用wglGetCurrentDC函數(shù)，就可以得到一個(gè)HDC了。具體的情況可以看下面的代碼。
第二個(gè)參數(shù)表示第一個(gè)要產(chǎn)生的字符，因?yàn)槲覀円a(chǎn)生0到127的字符的顯示列表，所以這里填0。
第三個(gè)參數(shù)表示要產(chǎn)生字符的總個(gè)數(shù)，因?yàn)槲覀円a(chǎn)生0到127的字符的顯示列表，總共有128個(gè)字符，所以這里填128。
第四個(gè)參數(shù)表示第一個(gè)字符所對(duì)應(yīng)顯示列表的編號(hào)。假如這里填1000，則第一個(gè)字符的繪制命令將被裝到第1000號(hào)顯示列表，第二個(gè)字符的繪制命令將被裝到第1001號(hào)顯示列表，依次類推。我們可以先用glGenLists申請(qǐng)128個(gè)連續(xù)的顯示列表編號(hào)，然后把第一個(gè)顯示列表編號(hào)填在這里。
還要說(shuō)明一下，因?yàn)?font style="LINE-HEIGHT: 21px; WORD-WRAP: normal; WORD-BREAK: normal" face="Times New Roman">wglUseFontBitmaps是Windows系統(tǒng)特有的函數(shù)，所以在使用前需要加入頭文件：#include <windows.h>。
現(xiàn)在讓我們來(lái)看具體的代碼：

#include <windows.h>

// ASCII字符總共只有0到127，一共128種字符
#define MAX_CHAR       128

void drawString(const char* str) {
    static int isFirstCall = 1;
    static GLuint lists;

    if( isFirstCall ) { // 如果是第一次調(diào)用，執(zhí)行初始化
                        // 為每一個(gè)ASCII字符產(chǎn)生一個(gè)顯示列表
        isFirstCall = 0;

        // 申請(qǐng)MAX_CHAR個(gè)連續(xù)的顯示列表編號(hào)
        lists = glGenLists(MAX_CHAR);

        // 把每個(gè)字符的繪制命令都裝到對(duì)應(yīng)的顯示列表中
        wglUseFontBitmaps(wglGetCurrentDC(), 0, MAX_CHAR, lists);
    }
    // 調(diào)用每個(gè)字符對(duì)應(yīng)的顯示列表，繪制每個(gè)字符
    for(; *str!='\0'; ++str)
        glCallList(lists + *str);
}

顯示列表一旦產(chǎn)生就一直存在（除非調(diào)用glDeleteLists銷毀），所以我們只需要在第一次調(diào)用的時(shí)候初始化，以后就可以很方便的調(diào)用這些顯示列表來(lái)繪制字符了。
繪制字符的時(shí)候，可以先用glColor*等指定顏色，然后用glRasterPos*指定位置，最后調(diào)用顯示列表來(lái)繪制。

void display(void) {
    glClear(GL_COLOR_BUFFER_BIT);

    glColor3f(1.0f, 0.0f, 0.0f);
    glRasterPos2f(0.0f, 0.0f);
    drawString("Hello, World!");

    glutSwapBuffers();
}
效果如圖：

指定字體
在產(chǎn)生顯示列表前，Windows允許選擇字體。
我做了一個(gè)selectFont函數(shù)來(lái)實(shí)現(xiàn)它，大家可以看看代碼。

void selectFont(int size, int charset, const char* face) {
    HFONT hFont = CreateFontA(size, 0, 0, 0, FW_MEDIUM, 0, 0, 0,
        charset, OUT_DEFAULT_PRECIS, CLIP_DEFAULT_PRECIS,
        DEFAULT_QUALITY, DEFAULT_PITCH | FF_SWISS, face);
    HFONT hOldFont = (HFONT)SelectObject(wglGetCurrentDC(), hFont);
    DeleteObject(hOldFont);
}

void display(void) {
    selectFont(48, ANSI_CHARSET, "Comic Sans MS");

    glClear(GL_COLOR_BUFFER_BIT);

    glColor3f(1.0f, 0.0f, 0.0f);
    glRasterPos2f(0.0f, 0.0f);
    drawString("Hello, World!");

    glutSwapBuffers();
}

最主要的部分就在于那個(gè)參數(shù)超多的CreateFont函數(shù)，學(xué)過(guò)Windows GDI的朋友應(yīng)該不會(huì)陌生。沒(méi)有學(xué)過(guò)GDI的朋友，有興趣的話可以自己翻翻MSDN文檔。這里我并不準(zhǔn)備仔細(xì)講這些參數(shù)了，下面的內(nèi)容還多著呢:(
如果需要在自己的程序中選擇字體的話，把selectFont函數(shù)抄下來(lái)，在調(diào)用glutCreateWindow之后、在調(diào)用wglUseFontBitmaps之前使用selectFont函數(shù)即可指定字體。函數(shù)的三個(gè)參數(shù)分別表示了字體大小、字符集（英文字體可以用ANSI_CHARSET，簡(jiǎn)體中文字體可以用GB2312_CHARSET，繁體中文字體可以用CHINESEBIG5_CHARSET，對(duì)于中文的Windows系統(tǒng)，也可以直接用DEFAULT_CHARSET表示默認(rèn)字符集）、字體名稱。
效果如圖：

 

轉(zhuǎn)載：http://blog.csdn.net/xie_zi/archive/2007/12/09/1925778.aspx
GLUT教程              鼠標(biāo)
在前幾節(jié)，我們看了怎么使用GLUT的keyboard函數(shù)，來(lái)增加一個(gè)OpenGL程序的交互性。現(xiàn)在，是時(shí)候研究下鼠標(biāo)了。GLUT的鼠標(biāo)接口提供一些列的選項(xiàng)來(lái)增加鼠標(biāo)的交互性。也就是檢測(cè)鼠標(biāo)單擊，和鼠標(biāo)移動(dòng)。
 
檢測(cè)鼠標(biāo)Clicks
和鍵盤處理一樣，GLUT為你的注冊(cè)函數(shù)（也就是處理鼠標(biāo)clicks事件的函數(shù)）提供了一個(gè)方法。函數(shù)glutMouseFunc,這個(gè)函數(shù)一般在程序初始化階段被調(diào)用。函數(shù)原型如下：
void glutMouseFunc(void(*func)(int button,int state,int x,int y));
參數(shù)：
func：處理鼠標(biāo)click事件的函數(shù)的函數(shù)名。
從上面可以看到到，處理鼠標(biāo)click事件的函數(shù)，一定有4個(gè)參數(shù)。第一個(gè)參數(shù)表明哪個(gè)鼠標(biāo)鍵被按下或松開(kāi)，這個(gè)變量可以是下面的三個(gè)值中的一個(gè)：
GLUT_LEFT_BUTTON
GLUT_MIDDLE_BUTTON
GLUT_RIGHT_BUTTON
第二個(gè)參數(shù)表明，函數(shù)被調(diào)用發(fā)生時(shí)，鼠標(biāo)的狀態(tài)，也就是是被按下，或松開(kāi)，可能取值如下：
GLUT_DOWN
GLUT_UP
當(dāng)函數(shù)被調(diào)用時(shí)，state的值是GLUT_DOWN，那么程序可能會(huì)假定將會(huì)有個(gè)GLUT_UP事件，甚至鼠標(biāo)移動(dòng)到窗口外面，也如此。然而，如果程序調(diào)用glutMouseFunc傳遞NULL作為參數(shù)，那么GLUT將不會(huì)改變鼠標(biāo)的狀態(tài)。
 
剩下的兩個(gè)參數(shù)（x,y）提供了鼠標(biāo)當(dāng)前的窗口坐標(biāo)（以左上角為原點(diǎn)）。
 
檢測(cè)動(dòng)作（motion）
GLUT提供鼠標(biāo)motion檢測(cè)能力。有兩種GLUT處理的motion：active motion和passive motion。Active motion是指鼠標(biāo)移動(dòng)并且有一個(gè)鼠標(biāo)鍵被按下。Passive motion是指當(dāng)鼠標(biāo)移動(dòng)時(shí)，并有沒(méi)鼠標(biāo)鍵按下。如果一個(gè)程序正在追蹤鼠標(biāo)，那么鼠標(biāo)移動(dòng)期間，沒(méi)一幀將產(chǎn)生一個(gè)結(jié)果。
 
和以前一樣，你必須注冊(cè)將處理鼠標(biāo)事件的函數(shù)（定義函數(shù)）。GLUT讓我們可以指定兩個(gè)不同的函數(shù)，一個(gè)追蹤passive motion，另一個(gè)追蹤active motion
 
它們的函數(shù)原型，如下：
void glutMotionFunc(void(*func)(int x,int y));
void glutPassiveMotionFunc(void (*func)(int x,int y));
參數(shù)：
Func：處理各自類型motion的函數(shù)名。
處理motion的參數(shù)函數(shù)的參數(shù)（x,y）是鼠標(biāo)在窗口的坐標(biāo)。以左上角為原點(diǎn)。
 
檢測(cè)鼠標(biāo)進(jìn)入或離開(kāi)窗口
GLUT還能檢測(cè)鼠標(biāo)鼠標(biāo)離開(kāi)，進(jìn)入窗口區(qū)域。一個(gè)回調(diào)函數(shù)可以被定義去處理這兩個(gè)事件。GLUT里，調(diào)用這個(gè)函數(shù)的是glutEntryFunc,函數(shù)原型如下：
void glutEntryFunc(void(*func)（int state）);
參數(shù)：
Func：處理這些事件的函數(shù)名。
上面函數(shù)的參數(shù)中，state有兩個(gè)值：
GLUT_LEFT
GLUT_ENTERED
表明，是離開(kāi)，還是進(jìn)入窗口。
 
把它們放一起
首先我們要做的是在GLUT里定義哪些函數(shù)將負(fù)責(zé)處理鼠標(biāo)事件。因此我們將重寫我們的main函數(shù)，讓它包含所有必須的回調(diào)注冊(cè)函數(shù)。我們將在程序里描述其他一些教程里沒(méi)說(shuō)清楚的地方。
void main(int argc, char **argv) {         glutInit(&argc, argv);         glutInitDisplayMode(GLUT_DEPTH | GLUT_DOUBLE | GLUT_RGBA);         glutInitWindowPosition(100,100);         glutInitWindowSize(320,320);         glutCreateWindow("SnowMen");         glutDisplayFunc(renderScene);         glutIdleFunc(renderScene);         glutReshapeFunc(changeSize);          //adding here the mouse processing callbacks         glutMouseFunc(processMouse);         glutMotionFunc(processMouseActiveMotion);         glutPassiveMotionFunc(processMousePassiveMotion);         glutEntryFunc(processMouseEntry);                  glutMainLoop();}OK，現(xiàn)在做點(diǎn)有趣的。我們將定義那些將做一些不可思議事件的回調(diào)函數(shù)。當(dāng)一個(gè)鼠標(biāo)鍵和alt鍵都被按下，我們將改變?nèi)切蔚念伾Ｊ髽?biāo)左鍵使三角形變成紅色，中間的將三角形變成綠色，鼠標(biāo)右鍵將三角形變成藍(lán)色。函數(shù)如下：
void processMouse(int button, int state, int x, int y) {           specialKey = glutGetModifiers();         // 當(dāng)鼠標(biāo)鍵和alt鍵都被按下         if ((state == GLUT_DOWN) &&                           (specialKey == GLUT_ACTIVE_ALT)) {                  // set the color to pure red for the left button                 if (button == GLUT_LEFT_BUTTON) {                          red = 1.0; green = 0.0; blue = 0.0;                 }                 // set the color to pure green for the middle button                 else if (button == GLUT_MIDDLE_BUTTON) {                          red = 0.0; green = 1.0; blue = 0.0;                 }                 // set the color to pure blue for the right button                 else {                          red = 0.0; green = 0.0; blue = 1.0;                 }         }}接下來(lái)有一個(gè)精細(xì)的顏色拾取方法。當(dāng)一個(gè)鼠標(biāo)鍵被按下，但alt鍵被被按下。我們把blue設(shè)為0.0，并且讓red和green分量的值取決于鼠標(biāo)在窗口中的位置。。函數(shù)如下：
void processMouseActiveMotion(int x, int y) {          // the ALT key was used in the previous function         if (specialKey != GLUT_ACTIVE_ALT) {                 // setting red to be relative to the mouse                  // position inside the window                 if (x < 0)                          red = 0.0;                 else if (x > width)                          red = 1.0;                 else                          red = ((float) x)/height;                 // setting green to be relative to the mouse                  // position inside the window                 if (y < 0)                          green = 0.0;                 else if (y > width)                          green = 1.0;                 else                          green = ((float) y)/height;                 // removing the blue component.                 blue = 0.0;         }}下面給passive motion添加一些動(dòng)作。當(dāng)shift鍵被按下，鼠標(biāo)將在x軸上有一個(gè)旋轉(zhuǎn)。我們不得不修改renderScene函數(shù)。函數(shù)如下：
float angleX = 0.0;...void renderScene(void) {         glClear(GL_COLOR_BUFFER_BIT | GL_DEPTH_BUFFER_BIT);         glPushMatrix();         glRotatef(angle,0.0,1.0,0.0);                  // This is the line we added for the         // rotation on the X axis;         glRotatef(angleX,1.0,0.0,0.0);                  glColor3f(red,green,blue);          glBegin(GL_TRIANGLES);                 glVertex3f(-0.5,-0.5,0.0);                 glVertex3f(0.5,0.0,0.0);                 glVertex3f(0.0,0.5,0.0);         glEnd();         glPopMatrix();         angle++;         glutSwapBuffers();}現(xiàn)在我們的有個(gè)函數(shù)處理passive motion事件。函數(shù)將改變angleX的值。void processMousePassiveMotion(int x, int y) {          // User must press the SHIFT key to change the          // rotation in the X axis         if (specialKey != GLUT_ACTIVE_SHIFT) {                  // setting the angle to be relative to the mouse                  // position inside the window                 if (x < 0)                          angleX = 0.0;                 else if (x > width)                          angleX = 180.0;                 else                          angleX = 180.0 * ((float) x)/height;         }}最后鼠標(biāo)離開(kāi)窗口將使動(dòng)畫停止，為了做到這，我們也需要改變函數(shù)renderScene。// initially define the increase of the angle by 1.0;float deltaAngle = 1.0;...void renderScene(void) {         glClear(GL_COLOR_BUFFER_BIT | GL_DEPTH_BUFFER_BIT);         glPushMatrix();         glRotatef(angle,0.0,1.0,0.0);         glRotatef(angleX,1.0,0.0,0.0);         glColor3f(red,green,blue);          glBegin(GL_TRIANGLES);                 glVertex3f(-0.5,-0.5,0.0);                 glVertex3f(0.5,0.0,0.0);                 glVertex3f(0.0,0.5,0.0);         glEnd();         glPopMatrix();         // this is the new line         // previously it was: angle++;         angle+=deltaAngle;         glutSwapBuffers();}processMouseEntry是最后一個(gè)函數(shù)。注意，這個(gè)在微軟操作系統(tǒng)下可能工作的不是很好。void processMouseEntry(int state) {         if (state == GLUT_LEFT)                 deltaAngle = 0.0;         else                 deltaAngle = 1.0;}VC6.0工程可以在這里下載（glut8.zip）。 （到這里位置，鍵盤，鼠標(biāo)方面的控制講完了，下面就是菜單了。）（原文地址：http://www.lighthouse3d.com/opengl/glut/index.php?9）

本文來(lái)自CSDN博客，轉(zhuǎn)載請(qǐng)標(biāo)明出處：http://blog.csdn.net/xie_zi/archive/2007/12/09/1925778.aspx

【轉(zhuǎn)】http://dacuisworld.spaces.live.com/blog/cns!5194FC8976D233A0!1121.entry
重裝電腦之后按照以上方法可順利配置OpenGL編程環(huán)境！重裝了真好！

在VISUAL C++ 2008上配置OPENGL開(kāi)發(fā)環(huán)境

pku 1050 最大子矩陣和

題目大意：
給定一個(gè)N*N的矩陣，求其中一個(gè)子矩陣所有元素的和最大，輸出最大值。

題解：
    這道題很早就見(jiàn)過(guò)了，一直不會(huì)做，學(xué)了最大連續(xù)和，但是沒(méi)能成功遷移，看別人的解題報(bào)告也是很久才理解。
主要思想就是把二維的矩陣轉(zhuǎn)化成一位的數(shù)字串，然后求最大子串和。轉(zhuǎn)換的時(shí)候，為了保證最大子串構(gòu)成的是完整的矩形，所以串里的每一個(gè)元素都得是一列的和。枚舉子矩陣的起始行和高度，如從第i行開(kāi)始，到第j行結(jié)束，每一對(duì) i 和 j，對(duì)每一列(1~n)求和，然后求1~n串的最大子串和。

         最近被逼的不行了，所以動(dòng)真格的學(xué)動(dòng)規(guī)！先是把《程序設(shè)計(jì)導(dǎo)引及在線實(shí)踐》這本書里動(dòng)規(guī)的例題都看過(guò)、做過(guò)，本來(lái)想一道一道的做習(xí)題的，結(jié)果poj掛了。于是轉(zhuǎn)戰(zhàn)hdu，昨天做了一道三維樹(shù)狀數(shù)組，比較理解了，今天又繼續(xù)hdu的動(dòng)規(guī)，感覺(jué)做過(guò)的題型，換個(gè)背景再做能夠想到并且實(shí)現(xiàn)了，細(xì)節(jié)上還需注意。
hdu 1160 FatMouse's Speed
題目大意：
給定n只老鼠的體重w和速度s，求一個(gè)最長(zhǎng)的排列，使得這個(gè)排列中的老鼠體重嚴(yán)格遞增，速度嚴(yán)格遞減。題目看上去很像最長(zhǎng)上升子序列，只是這里的序列是可以打亂順序按體重排序的。

解題思路：
整體思路同最長(zhǎng)上升子序列。
1、按老鼠的體重遞增排序，當(dāng)老鼠的體重相等時(shí)按速度遞減排序。
2、f[j]表示前j只老鼠中最長(zhǎng)序列的長(zhǎng)度，狀態(tài)轉(zhuǎn)移方程為
      f[N]初始值為0；
      f[j]=max{ f[i] : 0<=i<j 且 s[j]<s[i] }+1;
      也就是說(shuō)，如果第j只老鼠是最長(zhǎng)序列中的話，那么它肯定比上一個(gè)在最長(zhǎng)序列中老鼠體重更大 ( j>i ) 且速度更小 ( s[j] < s[i] )。

代碼如下：

Java課留作業(yè)，要求實(shí)現(xiàn)“在Frame窗口中設(shè)計(jì)一個(gè)文本框和一個(gè)文本區(qū)域，文本框內(nèi)容改變時(shí)，將文本框中的內(nèi)容顯示在文本區(qū)域中”，這個(gè)問(wèn)題可害苦了我，查了好多方法都不行，還是對(duì)Java里面的類不了解啊。
解決辦法：
創(chuàng)建文本框時(shí)不要用JTextField, 因?yàn)檫@個(gè)類里面沒(méi)有addTextListener的方法，所以聲明文本框的時(shí)候應(yīng)該這樣寫：
    java.awt.TextField textField=new java.awt.TextField();  
然后再給 textField 加一個(gè)監(jiān)聽(tīng)器
    textField.addTextListener(new TextListener(){
            public void textValueChanged(TextEvent e){
                ta.setText(textField.getText());
            }
        });
就可以實(shí)時(shí)在文本域里顯示文本框的改變了。
⊙﹏⊙b汗，這個(gè)問(wèn)題糾結(jié)了好久
感謝koy師兄的鼎力支持和耐心講解，好人啊！

        現(xiàn)在才做這個(gè)決定其實(shí)已經(jīng)有些晚了，但是人就是這樣，可以早作打算的時(shí)候往往不知道該怎么打算，好在我習(xí)慣了很多事情都在最后時(shí)刻奮力爭(zhēng)取。過(guò)年這些天很多人都對(duì)我媽說(shuō)，該讓孩子出去見(jiàn)識(shí)見(jiàn)識(shí)，別攔著。媽媽也想開(kāi)了，有了她的支持比任何利益誘惑都更能堅(jiān)定我。于是我想給自己找一個(gè)不得不出國(guó)的理由，然后堅(jiān)定信念去拼最后半年，但是我發(fā)現(xiàn)這個(gè)理由好難找，后來(lái)我知道了，很多事情之所以這樣做并不一定是出于必然，而是個(gè)人的喜好和性格，這樣的話，選擇就無(wú)所謂對(duì)錯(cuò)，只有喜歡與否。就像選專業(yè)一樣，選到喜歡的就是對(duì)的。好吧，那就讓自己離開(kāi)家吧，像去杭州和哈爾濱一樣，下了火車沒(méi)感覺(jué)有多遠(yuǎn)，照樣是人們生活的地方。
        我的學(xué)分也漸漸上來(lái)了，競(jìng)賽也有了一些成果，接下來(lái)該做的事情就是考英語(yǔ)的G、T和完成實(shí)驗(yàn)室Vuze的項(xiàng)目，最好能發(fā)一篇論文，保持成績(jī)和競(jìng)賽。時(shí)間緊，任務(wù)重，沒(méi)有心思想別的了，努力吧：）
       新年新愿望：明年的這個(gè)時(shí)候希望有好的offer圓了我的留學(xué)夢(mèng)^-^

包含點(diǎn)集所有點(diǎn)的最小圓的算法最小圓覆蓋 http://acm.zju.edu.cn/show_problem.php?pid=1450 相關(guān)題目最小球包含 http://acm.pku.edu.cn/JudgeOnline/problem?id=2069 平面上有n個(gè)點(diǎn)，給定n個(gè)點(diǎn)的坐標(biāo)，試找一個(gè)半徑最小的圓，將n 個(gè)點(diǎn)全部包圍，點(diǎn)可以在圓上。 1. 在點(diǎn)集中任取3點(diǎn)A,B,C。 2. 作一個(gè)包含A,B,C三點(diǎn)的最小圓,圓周可能通過(guò)這3點(diǎn)，也可能只通過(guò)其中兩點(diǎn),但包含第3點(diǎn).后一種情況圓周上的兩點(diǎn)一定是位于圓的一條直徑的兩端。 3. 在點(diǎn)集中找出距離第2步所建圓圓心最遠(yuǎn)的D點(diǎn)，若D點(diǎn)已在圓內(nèi)或圓周上，則該圓即為所求的圓，算法結(jié)束.則，執(zhí)行第4步。 4. 在A,B,C,D中選3個(gè)點(diǎn),使由它們生成的一個(gè)包含這4個(gè)點(diǎn)的圓為最小，這3 點(diǎn)成為新的A,B,C，返回執(zhí)行第2步。若在第4步生成的圓的圓周只通過(guò)A,B,C,D 中的兩點(diǎn)，則圓周上的兩點(diǎn)取成新的A和B,從另兩點(diǎn)中任取一點(diǎn)作為新的C。 程序設(shè)計(jì)題解上的解題報(bào)告：對(duì)于一個(gè)給定的點(diǎn)集A，記MinCircle(A)為點(diǎn)集A的最小外接圓，顯然，對(duì)于所有的點(diǎn)集情況A,MinCircle(A)都是存在且惟一的。需要特別說(shuō)明的是，當(dāng)A為空集時(shí)，MinCircle(A)為空集，當(dāng)A={a}時(shí)，MinCircle(A)圓心坐標(biāo)為a，半徑為0； 顯然，MinCircle(A)可以有A邊界上最多三個(gè)點(diǎn)確定(當(dāng)點(diǎn)集A中點(diǎn)的個(gè)數(shù)大于 1時(shí)，有可能兩個(gè)點(diǎn)確定了MinCircle(A))，也就是說(shuō)存在著一個(gè)點(diǎn)集B，|B|<=3 且B包含與A，有MinCircle(B)=MinCircle(A).所以，如果a不屬于B，則 MinCircle(A-{a})=MinCircle(A);如果MinCircle(A-{a})不等于MinCircle(A),則 a屬于B。 所以我們可以從一個(gè)空集R開(kāi)始，不斷的把題目中給定的點(diǎn)集中的點(diǎn)加入R，同時(shí)維護(hù)R的外接圓最小，這樣就可以得到解決該題的算法。
zju 1450
題目描述：給定n個(gè)點(diǎn)，求覆蓋所有點(diǎn)的圓的圓心和半徑

一個(gè)標(biāo)準(zhǔn)的Joseph問(wèn)題，n個(gè)人（編號(hào)0~(n-1))，從0開(kāi)始報(bào)數(shù)，報(bào)到(m-1)的退出，剩下的人繼續(xù)從0開(kāi)始報(bào)數(shù)。求勝利者的編號(hào)。
我們知道第一個(gè)人(編號(hào)一定是m%n-1) 出列之后，剩下的n-1個(gè)人組成了一個(gè)新的約瑟夫環(huán)（以編號(hào)為k=m%n的人開(kāi)始）:
   k   k+1   k+2   ... n-2, n-1, 0, 1, 2, ... k-2
并且從k開(kāi)始報(bào)0。

現(xiàn)在我們把他們的編號(hào)做一下轉(zhuǎn)換：
k      --> 0
k+1    --> 1
k+2    --> 2
...
...
k-2    --> n-2
k-1    --> n-1

變換后就完完全全成為了(n-1)個(gè)人報(bào)數(shù)的子問(wèn)題，假如我們知道這個(gè)子問(wèn)題的解：例如x是最終的勝利者，那么根據(jù)上面這個(gè)表把這個(gè)x變回去不剛好就是n個(gè)人情況的解嗎？！！變回去的公式很簡(jiǎn)單，相信大家都可以推出來(lái)：x'=(x+k)%n

如何知道(n-1)個(gè)人報(bào)數(shù)的問(wèn)題的解？對(duì)，只要知道(n-2)個(gè)人的解就行了。(n-2)個(gè)人的解呢？當(dāng)然是先求(n-3)的情況 ---- 這顯然就是一個(gè)倒推問(wèn)題！好了，思路出來(lái)了，下面寫遞推公式：

令f表示i個(gè)人玩游戲報(bào)m退出最后勝利者的編號(hào)，最后的結(jié)果自然是f[n]

遞推公式
f[1]=0;
f[i]=(f[i-1]+m)%i;   (i>1)

有了這個(gè)公式，我們要做的就是從1-n順序算出f的數(shù)值，最后結(jié)果是f[n]。因?yàn)閷?shí)際生活中編號(hào)總是從1開(kāi)始，我們輸出f[n]+1

由于是逐級(jí)遞推，不需要保存每個(gè)f，程序也比較簡(jiǎn)單：