典型的最近點對算法的應用，不過這個題多了個限制條件，就是點分為2類，最短距離必須在不同的類之間。為了滿足這個限制，只需要
把同類別點直接的距離都當作INF處理即可。
最近點對的算法，算導上面說是nlogn的。但是這個復雜度實現起來略微麻煩點，有一種實現方法是n*logn*logn的，其只對x坐標進行
了排序。n*logn的算法需要對x和y分量分別進行排序，還需要用到其它的輔助數組。
第一個題我用了n*logn算法實現了，第二個題則用了n*logn*logn算法實現了。但是時間上相差不大，因為第一個算法每次進行分治時
候消耗的O(n)時間也有幾次。第二個算法分治時候，需要再次排序的時間也不一定很多，因為可能數據量不夠大。
算法的本質就是二分按照X排序好的點數組，n*logn*logn變成n*logn的關鍵是預先對y也排序好一個點數組，因為按y排序好的點數組，
在分治后的合并中要用到。算法更詳細的解釋請參照算法導論。
poj 3714 代碼如下： #include <stdio.h>
#include <
string.h>
#include <math.h>
#include <algorithm>
using namespace std;
#define MAX_N (100000 * 2 + 10)
const double FINF = 1LL << 60;
struct Point
{
double x, y;
int nKind;
};
Point pts[MAX_N], ptsY[MAX_N], ptsTemp[MAX_N];
Point ptsSave[MAX_N];
int nNum;
bool CmpX(
const Point& a,
const Point& b)
{
return a.x < b.x;
}
bool CmpY(
const Point& a,
const Point& b)
{
return a.y < b.y;
}
double Dis(Point a, Point b)
{
if (a.nKind == b.nKind)
{
return FINF;
}
else {
return sqrt((a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y));
}
}
double FindMinDis(Point pts[], Point ptsY[], Point ptsTemp[],
int nBeg,
int nEnd)
{
if (nBeg == nEnd)
{
return FINF;
}
else if (nBeg + 1 == nEnd)
{
return Dis(pts[nBeg], pts[nEnd]);
}
else if (nBeg + 2 == nEnd)
{
return min(min(Dis(pts[nBeg], pts[nBeg + 1]), Dis(pts[nBeg], pts[nEnd])),
Dis(pts[nBeg + 1], pts[nEnd]));
}
else {
memcpy(ptsSave + nBeg, ptsY + nBeg,
sizeof(Point) * (nEnd - nBeg + 1));//保存當前的Y坐標順序
int nMid = (nBeg + nEnd) / 2;
int nL = nBeg;
int nR = nMid + 1;
for (
int i = nBeg; i <= nEnd; ++i)
{
if (ptsY[i].x - pts[nMid].x <= 0)
{
ptsTemp[nL++] = ptsY[i];
}
else {
ptsTemp[nR++] = ptsY[i];
}
}
double fAns = min(FindMinDis(pts, ptsTemp, ptsY, nBeg, nMid),
FindMinDis(pts, ptsTemp, ptsY, nMid + 1, nEnd));
int nK = 1;
for (
int i = nBeg; i <= nEnd; ++i)
{
if (fabs(ptsSave[i].x - pts[nMid].x) <= fAns)
{
ptsTemp[nK++] = ptsSave[i];
}
}
for (
int i = 1; i < nK; ++i)
{
for (
int j = i + 1; j < nK; ++j)
{
if (ptsTemp[j].y - ptsTemp[i].y > fAns)
{
break;
}
fAns = min(fAns, Dis(ptsTemp[i], ptsTemp[j]));
}
}
return fAns;
}
}
int main()
{
int nT;
int nN;
//printf("%f", FINF);
scanf("%d", &nT);
while (nT--)
{
scanf("%d", &nN);
nNum = nN * 2;
for (
int i = 0; i < nN; ++i)
{
scanf("%lf%lf", &pts[i].x, &pts[i].y);
pts[i].nKind = 1;
}
for (
int i = nN; i < nNum; ++i)
{
scanf("%lf%lf", &pts[i].x, &pts[i].y);
pts[i].nKind = 2;
}
memcpy(ptsY, pts,
sizeof(Point) * nNum);
sort(pts, pts + nNum, CmpX);
sort(ptsY, ptsY + nNum, CmpY);
printf("%.3f\n", FindMinDis(pts, ptsY, ptsTemp, 0, nNum - 1));
}
return 0;
}
hdu 1007 代碼如下：
#include <stdio.h>
#include <math.h>
#include <algorithm>
using namespace std;
#define MAX (100000 + 10)
struct Point
{
double x, y;
};
Point pts[MAX];
Point ptsTemp[MAX];
const double FINF = 1LL << 60;
bool CmpX(
const Point& a,
const Point& b)
{
return a.x < b.x;
}
bool CmpY(
const Point& a,
const Point& b)
{
return a.y < b.y;
}
double Dis(Point a, Point b)
{
return sqrt((a.x - b.x) * (a.x - b.x) + (b.y - a.y) * (b.y - a.y));
}
double Find(
int nL,
int nH)
{
if (nL == nH)
{
return FINF;
}
else if (nL + 1 == nH)
{
return Dis(pts[nL], pts[nH]);
}
else if (nL + 2 == nH)
{
return min(Dis(pts[nL], pts[nL + 1]),
min(Dis(pts[nL], pts[nH]), Dis(pts[nH], pts[nL + 1])));
}
else {
int nMid = (nL + nH) / 2;
double fAns = min(Find(nL, nMid), Find(nMid + 1, nH));
int nK = 0;
for (
int i = nL; i <= nH; ++i)
{
if (fabs(pts[i].x - pts[nMid].x) <= fAns)
{
ptsTemp[nK++] = pts[i];
}
}
sort(ptsTemp, ptsTemp + nK, CmpY);
for (
int i = 0; i < nK; ++i)
{
for (
int j = i + 1; j < nK; ++j)
{
if (ptsTemp[j].y - ptsTemp[i].y >= fAns)
{
break;
}
fAns = min(fAns, Dis(ptsTemp[j], ptsTemp[i]));
}
}
return fAns;
}
}
int main()
{
int nN;
while (scanf("%d", &nN), nN)
{
for (
int i = 0; i < nN; ++i)
{
scanf("%lf%lf", &pts[i].x, &pts[i].y);
}
sort(pts, pts + nN, CmpX);
printf("%.2f\n", Find(0, nN -1) * 0.5);
}
return 0;
}
題目意思是給出2條直線，然后判斷其是否相交，平行，還是重合。剛開始以為是判斷2條線段的關系，用了黑書的模板寫了，發現連樣例
都過不了。后面改了很多才過了。先判斷2條直線所在的向量是否平行，這個可以判斷這2個向量的叉積是否為0，然后再判斷線段是否重合，
可以選3點判斷叉積是否為0。如果向量不平行的話，直接求交點。求交點的公式是用了黑書里面的方法，先求出2個叉積代表2個三角形的
有向面積，然后根據定比分點的關系（面積的比例等于交點分其中一條線段的比例）可以推出計算公式。
有叉積和點積這2個工具確實能方便的解決很多問題。
代碼如下：
#include <stdio.h>
#include <string.h>
#include <math.h>
struct Point
{
double fX;
double fY;
};
Point beg[2], end[2];
int nN;
const double fPrecision = 1e-8;
double Det(double fX1, double fY1, double fX2, double fY2)
{
return fX1 * fY2 - fX2 * fY1;
}
double Cross(Point a, Point b, Point c)
{
return Det(b.fX - a.fX, b.fY - a.fY, c.fX - a.fX, c.fY - a.fY);
}
int DblCmp(double fD)
{
if (fabs(fD) < fPrecision)
{
return 0;
}
else
{
return (fD > 0 ? 1 : -1);
}
}
double DotDet(double fX1, double fY1, double fX2, double fY2)
{
return fX1 * fX2 + fY1 * fY2;
}
double Dot(Point a, Point b, Point c)
{
return DotDet(b.fX - a.fX, b.fY - a.fY, c.fX - a.fX, c.fY - a.fY);
}
int BetweenCmp(Point a, Point b, Point c)
{
return DblCmp(Dot(a, b, c));
}
int SegCross(Point a, Point b, Point c, Point d, Point& p)
{
double s1, s2, s3, s4;
int d1, d2, d3, d4;
d1 = DblCmp(s1 = Cross(a, b, c));
d2 = DblCmp(s2 = Cross(a, b, d));
d3 = DblCmp(s3 = Cross(c, d, a));
d4 = DblCmp(s4 = Cross(c, d, b));
Point e, f;
e.fX = a.fX - b.fX;
e.fY = a.fY - b.fY;
f.fX = c.fX - d.fX;
f.fY = c.fY - d.fY;
if (DblCmp(Det(e.fX, e.fY, f.fX, f.fY)) == 0)//2個向量共線
{
if (d1 * d2 > 0 && d3 * d4 > 0)//不在同一條直線上
{
return 0;
}
else
{
return 2;
}
}
//2條直線相交
p.fX = (c.fX * s2 - d.fX * s1) / (s2 - s1);
p.fY = (c.fY * s2 - d.fY * s1) / (s2 - s1);
return 1;
}
int main()
{
//freopen("out.txt", "w", stdout);
while (scanf("%d", &nN) == 1)
{
printf("INTERSECTING LINES OUTPUT\n");
Point p;
for (int i = 0; i < nN; ++i)
{
scanf("%lf%lf%lf%lf", &beg[0].fX, &beg[0].fY, &end[0].fX, &end[0].fY);
scanf("%lf%lf%lf%lf", &beg[1].fX, &beg[1].fY, &end[1].fX, &end[1].fY);
int nRet = SegCross(beg[0], end[0], beg[1], end[1], p);
if (nRet == 0)
{
printf("NONE\n");
}
else if (nRet == 1)
{
printf("POINT %.2f %.2f\n", p.fX, p.fY);
}
else
{
printf("LINE\n");
}
}
printf("END OF OUTPUT\n");
}
return 0;
}
這是一個計算幾何的題目。題意是，按順序給一系列的線段，問最終哪些線段處在頂端。
只需要窮舉判斷，當前的線段會與哪些線段有交點即可。也就是暴力求解，但是線段數目N有10的5次方，平方算法是不能過的。這個題
能過的原因是題目描述里面說了，top的stick不會超過1000個。那么修改下暴力的方式題目就能過了。
從小到大枚舉每個棍子，判斷它是否與后面的棍子相交，如果相交直接把當前棍子的top屬性置為false，然后break內層循環。這樣就不
會超時了，暴力也是需要技巧的，這句話說的很對啊。
判斷2條線段是否相交的算法直接按照黑書上的模板代碼寫了，那個模板代碼還不錯吧。。。
代碼如下：
#include <stdio.h>
#include <
string.h>
#include <math.h>
#define MAX_N (100000 + 10)
struct POS
{
double fX;
double fY;
};
POS begs[MAX_N], ends[MAX_N];
bool bAns[MAX_N];
int nN;
const double fPrecision = 1e-8;
double Det(
double fX1,
double fY1,
double fX2,
double fY2)
{
return fX1 * fY2 - fX2 * fY1;
}
//以a作為公共點,計算叉積
double Cross(POS& a, POS& b, POS& c)
{
return Det(b.fX - a.fX, b.fY - a.fY, c.fX - a.fX, c.fY - a.fY);
}
int DblCmp(
double fD)
{
if (fabs(fD) < fPrecision)
{
return 0;
}
else {
return fD > 0 ? 1 : -1;
}
}
//
bool IsSegCross(
int nI,
int nJ)
{
return (DblCmp(Cross(begs[nI], ends[nI], begs[nJ]))
^ DblCmp(Cross(begs[nI], ends[nI], ends[nJ]))) == -2
&& (DblCmp(Cross(begs[nJ], ends[nJ], begs[nI]))
^ DblCmp(Cross(begs[nJ], ends[nJ], ends[nI]))) == -2;
}
int main()
{
while (scanf("%d", &nN), nN)
{
for (
int i = 1; i <= nN; ++i)
{
scanf("%lf%lf%lf%lf", &begs[i].fX, &begs[i].fY,
&ends[i].fX, &ends[i].fY);
}
memset(bAns,
true,
sizeof(bAns));
//暴力也是需要技巧的
for (
int i = 1; i < nN; ++i)
{
for (
int j = i + 1; j <= nN; ++j)
{
if (IsSegCross(i, j))
{
bAns[i] =
false;
break;
}
}
}
printf("Top sticks:");
bool bPre =
false;
for (
int i = 1; i <= nN; ++i)
{
if (bAns[i])
{
if (bPre)
{
printf(",");
}
bPre =
true;
printf(" %d", i);
}
}
printf(".\n");
}
return 0;
}
這個題不錯，居然需要在dfs里面寫bfs。題意類似于圖像識別里面，搜索一張圖像里面的某個指定區域里面有幾個斑點，題意里面的斑點是指色子。
30 15
..............................
..............................
...............*..............
...*****......****............
...*X***.....**X***...........
...*****....***X**............
...***X*.....****.............
...*****.......*..............
..............................
........***........******.....
.......**X****.....*X**X*.....
......*******......******.....
.....****X**.......*X**X*.....
........***........******.....
..............................
比如上面這個30 * 15的圖片里面，一共有四個區域，*作為區域的底色，然后是求區域里面有多少個X的塊。這個題單純dfs的話，很沒辦法，因為無法一次性把連接在一起的X都搜索了。比如，
5 5
XXX*X
XXX*X
.....
X***X
XX***
的時候，dfs很明顯就會出現問題，因為會先離開X塊，再次回到X塊，計數就會出現問題了。因此只能遇到X的時候，進行一次bfs，將與其相連接的X全部搜索掉。。。并且找到與當前X塊相連接的一個*的位置，如果有這樣的位置，就繼續進行dfs。
代碼如下：
#include <stdio.h>
#include <
string.h>
#include <algorithm>
#include <queue>
using namespace std;
int nW, nH;
char szData[100][100];
bool bVisit[100][100];
int nNum;
int nDice[100];
int nAdd[4][2] = {{0, -1}, {-1, 0}, {0, 1}, {1, 0}};
bool IsPosOk(
int i,
int j)
{
return i >= 0 && i < nH && j >= 0 && j < nW;
}
struct POS
{
int nI;
int nJ;
};
bool Bfs(
int& nI,
int& nJ)
{
bool bRet =
false;
queue<POS> qp;
POS pos = {nI, nJ};
int i = nI, j = nJ;
qp.push(pos);
while (qp.empty() ==
false)
{
POS head = qp.front();
qp.pop();
for (
int m = 0; m < 4; ++m)
{
int nNextI = head.nI + nAdd[m][0];
int nNextJ = head.nJ + nAdd[m][1];
if (IsPosOk(nNextI, nNextJ) && bVisit[nNextI][nNextJ] ==
false)
{
if (szData[nNextI][nNextJ] == 'X')
{
bVisit[nNextI][nNextJ] =
true;
POS pos = {nNextI, nNextJ};
qp.push(pos);
}
else if (szData[nNextI][nNextJ] == '*')
{
bRet =
true;
nI = nNextI;// 這里是返回新的dfs位置
nJ = nNextJ;
}
}
}
}
return bRet;
}
void dfs(
int i,
int j,
int nNum)
{
bVisit[i][j] =
true;
if (szData[i][j] == 'X')
{
nDice[nNum]++;
bool bDfs = Bfs(i, j);
//擴散掉當前連通的所有'X'
if (bDfs ==
false)
{
return;
}
else {
dfs(i, j, nNum);
}
}
for (
int m = 0; m < 4; ++m)
{
int nNextI = i + nAdd[m][0];
int nNextJ = j + nAdd[m][1];
if (IsPosOk(nNextI, nNextJ) && bVisit[nNextI][nNextJ] ==
false && szData[nNextI][nNextJ] != '.')
{
dfs(nNextI, nNextJ, nNum);
}
}
}
int main()
{
int nCases = 1;
while (scanf("%d%d", &nW, &nH), nW + nH)
{
for (
int i = 0; i < nH; ++i)
{
scanf("%s", szData[i]);
}
memset(bVisit,
false,
sizeof(bVisit));
memset(nDice, 0,
sizeof(nDice));
nNum = 0;
for (
int i = 0; i < nH; ++i)
{
for (
int j = 0; j < nW; ++j)
{
if (szData[i][j] == 'X' && bVisit[i][j] ==
false)
{
dfs(i, j, nNum);
nNum++;
}
}
}
sort(nDice, nDice + nNum);
printf("Throw %d\n", nCases++);
for (
int i = 0; i < nNum; ++i)
{
printf("%d%s", nDice[i], i == nNum - 1 ? "\n" : " ");
}
printf("\n");
}
return 0;
}
這是一個貌似很麻煩的題，題目要求是將一顆用ascii碼繪畫出來的樹，轉換為其一種字符串表示，這種字符串表示好像是叫做什么廣義表
什么的。
比如，
A |
--------
B C D
| |
----- -
E F G 對應的字符串表示 (A(B()C(E()F())D(G())))
比較糾結的是如何讀取數據，如何遞歸，如果建立樹的話，也麻煩，因為還是顆不定叉的樹。最主要的是如何方便地遞歸。最后知道了一個
比較巧妙的方法，先一次性把一組數據讀入字符串數組里面，再在這個字符串數組上進行遞歸處理。這樣的話，就能很方便的找到樹里面節點
的關系了。
而一次讀一個字符就想進行遞歸是沒辦法確定節點的關系的，不遞歸估計更很難寫，完全沒頭緒。。。
代碼如下：
1 #include <stdio.h>
2 #include <string.h>
3
4 char szLines[210][210];
5 int nNumOfLine;
6
7 void GetAns(int i, int j)
8 {
9 //printf("i:%d, j:%d, %c\n", i, j, szLines[i][j]);
10
11 if (szLines[i][j] != '\0')
12 {
13 putchar(szLines[i][j]);
14 //printf("%c", szLines[i + 1][j]);
15 if (szLines[i + 1][j] == '|')
16 {
17 int nBeg, nEnd;
18 nBeg = nEnd = j;
19 while (nBeg >= 0 && szLines[i + 2][nBeg] == '-')
20 {
21 --nBeg;
22 }
23 while (szLines[i + 2][nEnd] == '-')
24 {
25 ++nEnd;
26 }
27 //printf("nBeg:%d, nEnd:%d\n", nBeg, nEnd);
28 putchar('(');
29 for (int k = nBeg; k <= nEnd; ++k)
30 {
31 if (szLines[i + 3][k] != ' ' && szLines[i + 3][k] != '\0')
32 {
33 GetAns(i + 3, k);
34 }
35 }
36 putchar(')');
37 }
38 else
39 {
40 printf("()");
41 }
42 }
43
44 }
45
46 int main()
47 {
48 int nN;
49 char ch;
50
51 scanf("%d", &nN);
52 getchar();
53 while (nN--)
54 {
55 nNumOfLine = 0;
56 memset(szLines, 0, sizeof(szLines));
57 while (gets(szLines[nNumOfLine]), szLines[nNumOfLine][0] != '#')
58 {
59 //printf("%s\n", szLines[nNumOfLine]);
60 nNumOfLine++;
61 }
62 if (nNumOfLine == 0)
63 {
64 printf("()\n");
65 continue;
66 }
67 int i, j;
68 i = 0;
69 for (j = 0; szLines[0][j] == ' '; ++j);
70 //printf("i:%d, j:%d\n", i, j);
71 putchar('(');
72 GetAns(i, j);
73 putchar(')');
74 putchar('\n');
75 }
76
77 return 0;
78 }
79
這個題目的意思是要計算一些c語言表達式的值。這些表達式有+-還有++，--操作符與a-z這些變量組合而成。a-z的權值是1-26。
比如，表達式
c+f--+--a，得出值是9，其它變量的值也需要計算出來。 這個題目感覺比較麻煩，剛開始一點思路也沒有，還寫了個錯誤的方法，浪費了時間。
后面我的思路是 （+，-） （--，++）（變量）（--，++），這個匹配式子的意思是先處理二元操作符，然后處理前置，再處理變量，
再處理后置，如果發現沒有后置操作符，則把讀取的數據重新寫回數據流里面，下次再處理。
代碼如下：
1 #include <stdio.h>
2 #include <
string.h>
3 #include <sstream>
4 #include <algorithm>
5 using namespace std;
6 struct INFO
7 {
8 char ch;
9 int nValue;
10 char chAdd;
11 bool operator < (
const INFO& info)
const 12 {
13 return ch < info.ch;
14 }
15 };
16 17 INFO infos[200];
18 char szLine[200];
19 20 bool GetNextChar(stringstream& ss,
char& ch)
21 {
22 while (ss >> ch)
23 {
24 if (ch != ' ');
25 {
26 return true;
27 }
28 }
29 return false;
30 }
31 32 int main()
33 {
34 while (gets(szLine))
35 {
36 printf("Expression: %s\n", szLine);
37 memset(infos, 0,
sizeof(infos));
38 stringstream ss(szLine);
39 char ch;
40 int nNum = 0;
41 int nValue = 0;
42 char chOper;
43 bool bOk =
true;
44 bool bFirst =
true;
45 while (1)
46 {
47 if (bFirst)
48 {
49 chOper = '+';
50 bFirst =
false;
51 }
52 else 53 {
54 bOk = GetNextChar(ss, ch);
55 if (!bOk)
break;
56 chOper = ch;
57 }
58 59 bOk = GetNextChar(ss, ch);
60 if (!bOk)
break;
61 62 if (ch == '-')
//前置--
63 {
64 bOk = GetNextChar(ss, ch);
65 if (!bOk)
break;
//-
66 bOk = GetNextChar(ss, ch);
67 if (!bOk)
break;
//讀取字母
68 69 infos[nNum].ch = ch;
70 infos[nNum].nValue = ch - 'a';
71 72 if (chOper == '+')
73 {
74 nValue += infos[nNum].nValue;
75 }
76 else 77 {
78 nValue -= infos[nNum].nValue;
79 }
80 ++nNum;
81 }
82 else if (ch == '+')
//前置++
83 {
84 bOk = GetNextChar(ss, ch);
85 if (!bOk)
break;
//+
86 bOk = GetNextChar(ss, ch);
87 if (!bOk)
break;
//讀取字母
88 89 infos[nNum].ch = ch;
90 infos[nNum].nValue = ch - 'a' + 2;
91 92 if (chOper == '+')
93 {
94 nValue += infos[nNum].nValue;
95 }
96 else 97 {
98 nValue -= infos[nNum].nValue;
99 }
100 ++nNum;
101 }
102 else103 {
104 infos[nNum].ch = ch;
105 infos[nNum].nValue = ch - 'a' + 1;
106 107 if (chOper == '+')
108 {
109 nValue += infos[nNum].nValue;
110 }
111 else112 {
113 nValue -= infos[nNum].nValue;
114 }
115 116 //讀取后置操作符
117 char chOne;
118 char chTwo;
119 bOk = GetNextChar(ss, chOne);
120 if (!bOk)
121 {
122 ++nNum;
123 break;
124 }
125 bOk = GetNextChar(ss, chTwo);
126 if (!bOk)
127 {
128 ++nNum;
129 break;
130 }
131 132 if (chOne == chTwo)
133 {
134 if (chOne == '+')
135 {
136 infos[nNum].chAdd = '+';
137 }
138 else139 {
140 infos[nNum].chAdd = '-';
141 }
142 }
143 else144 {
145 ss.putback(chTwo);
146 ss.putback(chOne);
147 }
148 ++nNum;
149 }
150 }
151 152 printf(" value = %d\n", nValue);
153 sort(infos, infos + nNum);
154 for (
int i = 0; i < nNum; ++i)
155 {
156 if (infos[i].chAdd == '+')
157 {
158 infos[i].nValue++;
159 }
160 else if (infos[i].chAdd == '-')
161 {
162 infos[i].nValue--;
163 }
164 printf(" %c = %d\n", infos[i].ch, infos[i].nValue);
165 }
166 }
167 168 return 0;
169 }
170
題意是用字符串描述的一棵四叉樹，讀取字符串獲得最終葉子節點的顏色。輸入是2個字符串，根據這2個字符串建立2個四叉樹。然后對于，指定位置的葉子節點，如果2顆樹的葉子顏色其中一個為黑色，那么ans++，輸出的就是ans。
類似樹形結構的東西，直接一個函數遞歸求解即可。函數參數，一般是字符串地址，當前位置，然后還有其它在遞歸時候需要用到的東西。
代碼如下：
1 #include <stdio.h>
2 #define BLACK (1)
3 #define WHITE (2)
4 #define MAX (32)
5 int nStateA[MAX][MAX];
6 int nStateB[MAX][MAX];
7
8 char szOne[10000];
9 char szTwo[10000];
10
11 void GetState(int nState[MAX][MAX], char* pszLine, int& nPos,
12 int nSize, int nX, int nY)
13 {
14 if (pszLine[nPos] == 'p')
15 {
16 ++nPos;
17 GetState(nState, pszLine, nPos, nSize / 2, nX + nSize / 2, nY);
18 GetState(nState, pszLine, nPos, nSize / 2, nX, nY);
19 GetState(nState, pszLine, nPos, nSize / 2, nX, nY + nSize / 2);
20 GetState(nState, pszLine, nPos, nSize / 2, nX + nSize / 2, nY + nSize / 2);
21 }
22 else
23 {
24 for (int i = nX; i < nX + nSize; ++i)
25 {
26 for (int j = nY; j < nY + nSize; ++j)
27 {
28 if (pszLine[nPos] == 'e')
29 {
30
31 nState[i][j] = WHITE;
32 }
33 else
34 {
35 nState[i][j] = BLACK;
36 }
37 }
38 }
39 ++nPos;
40 }
41 }
42
43 int main()
44 {
45 int nCases;
46
47 scanf("%d\n", &nCases);
48 while (nCases--)
49 {
50 gets(szOne);
51 gets(szTwo);
52 int nPos = 0;
53 GetState(nStateA, szOne, nPos, MAX, 0, 0);
54 nPos = 0;
55 GetState(nStateB, szTwo, nPos, MAX, 0, 0);
56 int nAns = 0;
57
58 for (int i = 0; i < MAX; ++i)
59 {
60 for (int j = 0; j < MAX; ++j)
61 {
62 if (nStateA[i][j] == BLACK || nStateB[i][j] == BLACK)
63 {
64 nAns++;
65 }
66 }
67 }
68 printf("There are %d black pixels.\n", nAns);
69 }
70
71 return 0;
72 }
73
這也是一個數學題，剛開始還真以為好難的樣子，需要用到什么數論的理論啊。其實，只要去找規律就行了。
題意是給出一個進制，一個數字的最低位，和另外的一個數字，比如10進制，第一個數字的最低位是7，第二個數字是4，
根據這些信息，和規則（XXXXX7 * 4 = 7XXXXX，例子
: 179487 * 4 = 717948 ）求出第一個數字的最小長度。這個
規則的意思是乘積是把第一個數字的最低位移動到最高位上去就行了。
貌似很難的樣子，其實用筆在紙上求一下XXXXX7 * 4 = 7XXXXX就會發現。XXXXX7的每一位都是能夠確定的，當然
順序是從最低位到最高位開始。因為知道最低位，所以次低位一定是最低位*第二個數%base。以此類推，遞歸下去即可。
最終條件是，沒有進位了，而且乘積+原來的進位==最低位。
我用的遞歸完全可以改成循環的形式，這樣速度應該會快些。
代碼如下：
#include <stdio.h>
int nBase;
int nTwo;
int nOneLow;
int GetMin(int nLow, int nCarry, int nNum)
{
//printf("nLow:%d, nCarry:%d, nNum:%d\n", nLow, nCarry, nNum);
int nTemp = nCarry + nLow * nTwo;
if (nTemp == nOneLow)
{
return nNum;
}
return GetMin(nTemp % nBase, nTemp / nBase, nNum + 1);
}
int main()
{
//freopen("out.txt", "w", stdout);
while (scanf("%d%d%d", &nBase, &nOneLow, &nTwo) == 3)
{
printf("%d\n", GetMin(nOneLow, 0, 0) + 1);
}
return 0;
}
這是一個很神的數學題吧?；旧线^這個題的很多都會wa10多次，而且這個題好像簡單的枚舉其中的一個指數值都能過，可能是
數據量比較小。
但是，這個題還是有數學的解法的。但是，即使找到了這個正確的解法，過題的話，也是一件很困難的事情。題意大致如下：一只貓，
高度為H，戴了一個帽子，帽子里面有N只貓（N是常數，且未知），同樣帽子里面的貓也戴了帽子，但是這些貓的高度變成了H / (N + 1)，
會向下取整。以此遞歸下去，直到最后的貓的高度都為1為止?，F在，給出H和高度為1的貓的數量。要求的是高度大于1的貓的數量，
以及所有貓的高度之和。
很別扭吧。通過上面的信息，得出2個式子。假設one代表為高度為1的貓的數量。one = N的n次。H >= (N + 1)的n次。注意第
二個式子不一定取等號，因為很多時候都是不能整除的?，F在要求N和n。2個方程解2個未知數，應該能解出來。但是，注意的是其中
一個還是不等式。。。
指數關系很多時候會轉換為對數的關系。所以，繼續求對數，有lgH >= n * lg(N + 1)。其中，由第一個式子可以得到n = lg(one)
/ lg(N)。那么最終轉換為：lgH >= (lg(one) / lgN) * lg(N + 1)。換個形式就是lgH / lg(One) >= lg(N + 1) / lgN?，F在，已經很
清晰了。因為，函數lg(N + 1) / lg(N) 是
單調遞減的。看到單調的函數，馬上就會知道可以二分了。意思是，我們可以二分出一個N讓
lg(N + 1) / lgN 最接近lgH / lg(One)，而且是小于lgH / lg(One)的。剩下的工作就只是求和而已了。
寫二分的時候，有一個地方可以注意一下。因為 lg(N + 1) / lgN 可能會出現除數為0的情況，所以可以進一步轉換為
lgH * lgN >=
lg(N + 1) * lg(one)。 也是求一個N讓上面那個不等式2邊的值最接近，而且右邊小于左邊。
能很快寫對這個題真不是件容易的事情。。。
代碼如下：
#include <stdio.h>
#include <math.h>
int main()
{
int nInitH, nOnes;
int nN, n;
while (scanf("%d%d", &nInitH, &nOnes), nInitH + nOnes)
{
int nBeg = 1;
int nEnd = nOnes;
int nMid;
while (nBeg <= nEnd)
{
nMid = (nBeg + nEnd) / 2;
double fRes = log10(nInitH) * log10(nMid);
double fTemp = log10(nMid + 1) * log10(nOnes);
if (fabs(fRes - fTemp) < 1e-10)
{
//printf("Find nN:%d\n", nMid);
nN = nMid;
break;
}
else if (fTemp > fRes)
{
nBeg = nMid + 1;
}
else
{
nEnd = nMid - 1;
}
}
n = floor(log10(nInitH) / log10(nN + 1) + 1e-9);
//printf("nN:%d, n:%d\n", nN, n);
int nSum = 0;
int nLazy = 0;
int nNum = 1;
for (int i = 0; i <= n; ++i)
{
nSum += nNum * nInitH;
nLazy += nNum;
nNum *= nN;
nInitH /= (nN + 1);
}
printf("%d %d\n", nLazy - nOnes, nSum);
}
return 0;
}
這是一個幾何題。題意是給出一系列點，點最多才15個，求一個這里面的三個點組合出來的三角形，其面積是最大的，而且沒有任何其它
的點在這個三角形的內部和邊界上。求三角形的面積，題目上面已經給了公式，也可以用0.5*|a|*|b|*sin(a,b)求，這里的a和b指的是2條
邊代表的向量。
現在就剩下一個問題了，怎么判斷一個點在三角形的內部和邊界上。在邊界上，比較好判斷，判斷是否共線，然后再點是在線段的內部。
具體說明下，判斷一個點在三角形內部的思路。我用的還是線性規劃的思想。
如果該點在三角形的內部，那么任取三角形的一條邊，
該內部點和剩余的三角形的一個頂點必定在三角形的那條的邊的同一側。這個方法也可以推廣到N邊的凸多邊形，證明的話很簡單，
因為線性規劃一直在劃分區域。所以，劃分到最后圍起來的區域就是凸多邊形的內部了。
至于寫代碼的話，由于是第一次寫這種幾何題，寫得很凌亂。
代碼如下：
#include <stdio.h>
#include <math.h>
#define MAX (20)
int nN;
struct Point
{
char szLabel[5];
int x;
int y;
};
Point points[MAX];
//三點是否共線
bool IsOneLine(int nOne, int nTwo, int nThree)
{
int nA = points[nTwo].x - points[nOne].x;
int nB = points[nTwo].y - points[nOne].y;
int nC = points[nThree].x - points[nOne].x;
int nD = points[nThree].y - points[nOne].y;
return (nA * nD == nB * nC);
}
//點nOne和點nTwo是否在直線(nBeg,nEnd)的同一側(不能在直線上)
bool IsSameSide(int nBeg, int nEnd, int nOne, int nTwo)
{
//求直線的向量
int nA = points[nBeg].x - points[nEnd].x;
int nB = points[nBeg].y - points[nEnd].y;
//直線方程為nB(x - points[nBeg].x) - nA(y - points[nBeg].y) = 0
//分別用nOne和nTwo的坐標代入直線方程計算結果，然后將結果相乘
//乘積必須大于0
int nRes = (nB * (points[nOne].x - points[nBeg].x) - nA * (points[nOne].y - points[nBeg].y))
* (nB * (points[nTwo].x - points[nBeg].x) - nA * (points[nTwo].y - points[nBeg].y));
if (nRes > 0)
{
//printf("點:%d,點:%d,在直線nBeg:%d, nEnd:%d的同一側\n", nOne, nTwo, nBeg, nEnd);
}
return nRes > 0;
}
//點是否在三角形(nOne, nTwo, nThree)外部
bool PointOutTriangle(int nOne, int nTwo, int nThree, int nPoint)
{
//前面3個ifelse是判斷點是否在邊上
if (IsOneLine(nOne, nTwo, nPoint))
{
if ((points[nOne].x - points[nPoint].x) * (points[nTwo].x - points[nPoint].x) <= 0)
{
return false;
}
}
else if (IsOneLine(nOne, nThree, nPoint))
{
if ((points[nOne].x - points[nPoint].x) * (points[nThree].x - points[nPoint].x) <= 0)
{
return false;
}
}
else if (IsOneLine(nTwo, nThree, nPoint))
{
if ((points[nTwo].x - points[nPoint].x) * (points[nThree].x - points[nPoint].x) <= 0)
{
return false;
}
}
//下面的IsSameSide如果nPoint在直線的(nOne,nTwo)的外側也會判斷為假
//所以需要先在上面判斷點是否在邊的內側
return !(IsSameSide(nOne, nTwo, nThree, nPoint)
&& IsSameSide(nOne, nThree, nTwo, nPoint)
&& IsSameSide(nTwo, nThree, nOne, nPoint));
}
bool IsValid(int nOne, int nTwo, int nThree)
{
if (IsOneLine(nOne, nTwo, nThree))
{
//printf("點:%d,%d,%d共線\n", nOne, nTwo, nThree);
return false;
}
for (int i = 0; i < nN; ++i)
{
if (i == nOne || i == nTwo || i == nThree)
{
continue;
}
if (!PointOutTriangle(nOne, nTwo, nThree, i))
{
//printf("點:%d, 在三角形:%d,%d,%d內部\n", i, nOne, nTwo, nThree);
return false;
}
}
return true;
}
//計算三角形(nOne, nTwo, nThree)的面積
double GetArea(int nOne, int nTwo, int nThree)
{
return 0.5 * fabs((points[nThree].y - points[nOne].y) * (points[nTwo].x - points[nOne].x)
- (points[nTwo].y - points[nOne].y) * (points[nThree].x - points[nOne].x));
}
int main()
{
while (scanf("%d", &nN), nN)
{
for (int i = 0; i < nN; ++i)
{
scanf("%s%d%d", points[i].szLabel, &points[i].x, &points[i].y);
}
double fMaxArea = 0.0;
int nI = -1, nJ = -1, nK = -1;
for (int i = 0; i < nN - 2; ++i)
{
for (int j = i + 1; j < nN - 1; ++j)
{
for (int k = j + 1; k < nN; ++k)
{
if (IsValid(i, j, k))
{
//printf("i:%d,j:%d,k:%d valid\n", i, j, k);
double fArea = GetArea(i, j, k);
//printf("Area:%f\n", fArea);
if (fArea > fMaxArea)
{
nI = i;
nJ = j;
nK = k;
fMaxArea = fArea;
}
}
}
}
}
printf("%s%s%s\n", points[nI].szLabel, points[nJ].szLabel, points[nK].szLabel);
}
return 0;
}