yx - C++博客

poj 3714 Raid and hdu 1007 Quoit Design

典型的最近点对算法的应用，不过这个题多了个限制条件，就是点分为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;
}

posted @ 2012-07-18 13:53 yx 阅读(1145) | 评论 (0) | 编辑收藏

poj 1269 Intersecting Lines

题目意思是给出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;
}

posted @ 2012-07-17 15:20 yx 阅读(1023) | 评论 (0) | 编辑收藏

poj 2653 Pick-up sticks

这是一个计算几何的题目。题意是，按顺序给一系列的线段，问最终哪些线段处在顶端。
只需要穷举判断，当前的线段会与哪些线段有交点即可。也就是暴力求解，但是线段数目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;
}

posted @ 2012-07-15 17:06 yx 阅读(980) | 评论 (0) | 编辑收藏

uva 657 - The die is cast

这个题不错，居然需要在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;
}

posted @ 2012-07-14 21:16 yx 阅读(937) | 评论 (0) | 编辑收藏

uva 10562 - Undraw the Trees

这是一个貌似很麻烦的题，题目要求是将一颗用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

posted @ 2012-07-10 21:35 yx 阅读(886) | 评论 (0) | 编辑收藏

uva 327 - Evaluating Simple C Expressions

这个题目的意思是要计算一些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             else
103             {
104                 infos[nNum].ch = ch;
105                 infos[nNum].nValue = ch - 'a' + 1;
106
107                 if (chOper == '+')
108                 {
109                     nValue += infos[nNum].nValue;
110                 }
111                 else
112                 {
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                     else
139                     {
140                         infos[nNum].chAdd = '-';
141                     }
142                 }
143                 else
144                 {
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

posted @ 2012-07-10 12:05 yx 阅读(1074) | 评论 (0) | 编辑收藏

uva 297 - Quadtrees

题意是用字符串描述的一棵四叉树，读取字符串获得最终叶子节点的颜色。输入是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

posted @ 2012-07-08 11:06 yx 阅读(980) | 评论 (0) | 编辑收藏

uva 550 - Multiplying by Rotation

这也是一个数学题，刚开始还真以为好难的样子，需要用到什么数论的理论啊。其实，只要去找规律就行了。
题意是给出一个进制，一个数字的最低位，和另外的一个数字，比如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;
}

posted @ 2012-05-08 16:24 yx 阅读(1420) | 评论 (0) | 编辑收藏

uva 107 - The Cat in the Hat

这是一个很神的数学题吧。基本上过这个题的很多都会wa10多次，而且这个题好像简单的枚举其中的一个指数值都能过，可能是
数据量比较小。
但是，这个题还是有数学的解法的。但是，即使找到了这个正确的解法，过题的话，也是一件很困难的事情。题意大致如下：一只猫，
高度为H，戴了一个帽子，帽子里面有N只猫（N是常数，且未知），同样帽子里面的猫也戴了帽子，但是这些猫的高度变成了H / (N + 1)，
会向下取整。以此递归下去，直到最后的猫的高度都为1为止。现在，给出H和高度为1的猫的数量。要求的是高度大于1的猫的数量，
以及所有猫的高度之和。
很别扭吧。通过上面的信息，得出2个式子。假设one代表为高度为1的猫的数量。one = N的n次。H >= (N + 1)的n次。注意第
二个式子不一定取等号，因为很多时候都是不能整除的。现在要求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。现在，已经很
清晰了。因为，函数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;
}

posted @ 2012-05-07 16:54 yx 阅读(1674) | 评论 (0) | 编辑收藏

uva 10112 - Myacm Triangles

这是一个几何题。题意是给出一系列点，点最多才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;
}

posted @ 2012-05-07 14:07 yx 阅读(1271) | 评论 (0) | 编辑收藏

poj 3714 Raid and hdu 1007 Quoit Design

poj 1269 Intersecting Lines

poj 2653 Pick-up sticks

uva 657 - The die is cast

uva 10562 - Undraw the Trees

uva 327 - Evaluating Simple C Expressions

uva 297 - Quadtrees

uva 550 - Multiplying by Rotation

uva 107 - The Cat in the Hat

uva 10112 - Myacm Triangles

导航

统计

公告

常用链接

留言簿(3)

随笔分类

随笔档案

me

好友

同学

网友

搜索

最新评论

阅读排行榜

评论排行榜