STEP BY STEP

发表于 分类于 ， 阅读次数： Valine：
本文字数： 1.7k 阅读时长 ≈ 2 分钟

此题用到了几个知识，一个是求多边形面积的公式。然后是，根据顶点都在整点上求多边形边界上的顶点数目的方法。最后一个是pick定理。根据前面2个信息和pick定理算出在多边形内部的整点的个数。
求多边形面积的方法还是叉积代表有向面积的原理，把原点看做另外的一个点去分割原来的多边形为N个三角形，然后把它们的有向面积加起来。
判断边界上点的个数是根据Gcd（dx,dy)代表当前边上整数点的个数的结论。这个结论的证明其实也比较简单，假设dx = a，dy = b。初始点是x0，y0，假设d = Gcd（a，b）。那么边上的点可以被表示为（x0 + k (a / d)，y0 + k （b / d))。为了使点是整数点，k必须是整数，而且0 求多边形内部点的个数用的是pick定理。面积 = 内部点 + 边界点 / 2 - 1。

代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <math.h>
using namespace std;
#define MAX (100 + 10)

struct Point
{
    double x, y;
};
Point pts[MAX];

int nN;
const int IN = 1;
const int EAGE = 2;
const int OUT = 3;
const double fPre = 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.x - a.x, b.y - a.y, c.x - a.x, c.y - a.y);
}

double GetArea()
{
    double fArea = 0.0;
    Point ori = {0.0, 0.0};

    for (int i = 0; i < nN; ++i)
    {
        fArea += Cross(ori, pts[i], pts[(i + 1) % nN]);
    }
    return fabs(fArea) * 0.5;
}

int gcd(int nX, int nY)
{
    if (nX < 0)
    {
        nX = -nX;
    }
    if (nY < 0)
    {
        nY = -nY;
    }
    if (nX < nY)
    {
        swap(nX, nY);
    }
    while (nY)
    {
        int nT = nY;
        nY = nX % nY;
        nX = nT;
    }
    return nX;
}

int main()
{
    int nT;
    int nI, nE;
    double fArea;

    scanf("%d", &nT);
    int dx ,dy;

    for (int i = 1; i <= nT; ++i)
    {
        scanf("%d", &nN);
        nI = nE = 0;
        pts[0].x = pts[0].y = 0;
        for (int j = 1; j <= nN; ++j)
        {
            scanf("%d%d", &dx, &dy);
            pts[j].x = pts[j - 1].x + dx;
            pts[j].y = pts[j - 1].y + dy;
            nE += gcd(dx, dy);
        }
        fArea = GetArea();
        nI = (fArea + 1) - nE / 2;
        printf("Scenario #%d:\n%d %d %.1f\n\n", i, nI, nE, fArea);
    }

    return 0;
}

发表于 分类于 ， 阅读次数： Valine：
本文字数： 3.1k 阅读时长 ≈ 3 分钟

转角法判断点和多边形的关系大家都知道，原理比较简单，在多边形内扫过的转角一定是360度，在边界上和外面则不一定。
实现起来也比较麻烦，浮点误差比较大，而且还要考虑些特殊情况。
在网上找到一种叫做改进弧长法的算法，原理和转角法类似，但是做了很多重要的改进。比如，计算转角改成了计算叉积，根据叉积决定旋转方向，还要根据计算下一个点的象限决定偏转多少，每次偏转的都是90度的倍数。该算法可以方便判断出点在多边形内，还是边界上，还是在多边形外面。

摘自别人对该算法的描述如下：
首先从该书中摘抄一段弧长法的介绍：“弧长法要求多边形是有向多边形，一般规定沿多边形的正向，边的左侧为多边形的内侧域。以被测点为圆心作单位圆，将全部有向边向单位圆作径向投影，并计算其中单位圆上弧长的代数和。若代数和为0，则点在多边形外部；若代数和为2π则点在多边形内部；若代数和为π，则点在多边形上。”
按书上的这个介绍，其实弧长法就是转角法。但它的改进方法比较厉害：将坐标原点平移到被测点P，这个新坐标系将平面划分为4个象限，对每个多边形顶点P ，只考虑其所在的象限，然后按邻接顺序访问多边形的各个顶点P，分析P和P[i+1]，有下列三种情况：
（1）P[i+1]在P的下一象限。此时弧长和加π/2；
（2）P[i+1]在P的上一象限。此时弧长和减π/2；
（3）P[i+1]在Pi的相对象限。首先计算f=y[i+1]x-x[i+1]y（叉积），若f=0，则点在多边形上；若f<0，弧长和减π；若f>0，弧长和加π。
最后对算出的代数和和上述的情况一样判断即可。实现的时候还有两点要注意，第一个是若P的某个坐标为0时，一律当正号处理；第二点是若被测点和多边形的顶点重合时要特殊处理。

以上就是书上讲解的内容，其实还存在一个问题。那就是当多边形的某条边在坐标轴上而且两个顶点分别在原点的两侧时会出错。如边(3,0)-(-3,0)，按以上的处理，象限分别是第一和第二，这样会使代数和加π/2，有可能导致最后结果是被测点在多边形外。而实际上被测点是在多边形上（该边穿过该点）。对于这点，我的处理办法是：每次算P和P[i+1]时，就计算叉积和点积，判断该点是否在该边上，是则判断结束，否则继续上述过程。这样牺牲了时间，但保证了正确性。
具体实现的时候，由于只需知道当前点和上一点的象限位置，所以附加空间只需O(1)。实现的时候可以把上述的“π/2”改成1，“π”改成2，这样便可以完全使用整数进行计算。不必考虑顶点的顺序，逆时针和顺时针都可以处理，只是最后的代数和符号不同而已。整个算法编写起来非常容易。

代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
#include <stdio.h>
#include <math.h>

#define MAX (100 + 10)
struct Point
{
    double x,y;
};

Point pts[MAX];
const int OUT = 0;
const int IN = 1;
const int EDGE = 2;
const double fPre = 1e-8;

int DblCmp(double fD)
{
    if (fabs(fD) < fPre)
    {
        return 0;
    }
    else
    {
        return fD > 0 ? 1 : -1;
    }
}

int GetQuadrant(Point p)
{
    return DblCmp(p.x) >= 0 ? (DblCmp(p.y) >= 0 ? 0 : 3) :
               (DblCmp(p.y) >= 0 ? 1 : 2);
}

double Det(double fX1, double fY1, double fX2, double fY2)
{
    return fX1 * fY2 - fX2 * fY1;
}

int PtInPolygon(Point* pts, int nN, Point p)
{
    int i, j, k;
    for (j = 0; j < nN; ++j)
    {
        pts[j].x -= p.x;
        pts[j].y -= p.y;
    }
    int nA1, nA2;
    int nSum = 0;
    nA1 = GetQuadrant(pts[0]);
    for (i = 0; i < nN; ++i)
    {
        k = (i + 1) % nN;
        if (DblCmp(pts[k].x) == 0  DblCmp(pts[k].y) == 0)
        {
            break;//与顶点重合
        }
        int nC = DblCmp(Det(pts[i].x, pts[i].y,
                            pts[k].x, pts[k].y));
        if (!nC  DblCmp(pts[i].x * pts[k].x) <= 0
                 DblCmp(pts[i].y * pts[k].y) <= 0)
        {
            break;//边上
        }
        nA2 = GetQuadrant(pts[k]);
        if ((nA1 + 1) % 4 == nA2)
        {
            nSum += 1;
        }
        else if ((nA1 + 2) % 4 == nA2)
        {
            if (nC > 0)
            {
                nSum += 2;
            }
            else
            {
                nSum -= 2;
            }
        }
        else if ((nA1 + 3) % 4 == nA2)
        {
            nSum -= 1;
        }
        nA1 = nA2;
    }

    for (j = 0; j < nN; ++j)
    {
        pts[j].x += p.x;
        pts[j].y += p.y;
    }

    if (i < nN)
    {
        return EDGE;
    }
    else if (nSum)//逆时针nSum == 4, 顺时针nSum == -4
    {
        return IN;
    }
    else
    {
        return OUT;
    }
}

int main()
{
    int nN, nM;
    int nCase = 1;

    while (scanf("%d%d", &nN, &nM), nN)
    {
        if (nCase > 1)
        {
            printf("\n");
        }

        for (int i = 0; i < nN; ++i)
        {
            scanf("%lf%lf", &pts[i].x, &pts[i].y);
        }
        printf("Problem %d:\n", nCase++);
        for (int i = 0; i < nM; ++i)
        {
            Point p;
            scanf("%lf%lf", p.x, p.y);
            if (PtInPolygon(pts, nN, p))
            {
                printf("Within\n");
            }
            else
            {
                printf("Outside\n");
            }
        }
    }

    return 0;
}

发表于 分类于 ， 阅读次数： Valine：
本文字数： 1.8k 阅读时长 ≈ 2 分钟

这个题用到2个计算几何算法。求解凸包和简单多边形面积。凸包算法详细解释见算法导论。求解多边形面积的思想是将多边形分解为三角形，一般是假设按顺序取多边形上面连续的2点与原点组合成一个三角形，依次下去用叉积求有向面积之和，最后取绝对值即可。注意，这些点必须是在多边形上逆时针或者顺时针给出的，而求出凸包刚好给了这样的一系列点。
凸包代码，其实先找出一个y坐标最小的点，再对剩下的所有点按极角排序。然后对排序后的点进行一个二维循环即可。二维循环的解释是当加入新的点进入凸包集合时候，如果与以前加入的点形成的偏转方向不一致，那么前面那些点都需要弹出集合。

代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <math.h>
using namespace std;
#define MAX_N (10000 + 10)

struct Point
{
    double x, y;
    bool operator <(const Point p) const
    {
        return y < p.y || y == p.y  x < p.x;
    }
};

Point pts[MAX_N];
int nN;
Point ans[MAX_N];
int nM;

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.x - a.x, b.y - a.y, c.x - a.x, c.y - a.y);
}

bool CrossCmp(const Point a, const Point b)
{
    double cs = Cross(pts[0], a, b);
    return cs > 0 || cs == 0  a.x < b.x; 
}

void Scan()
{
    nM = 0;
    sort(pts + 1, pts + nN, CrossCmp);//对所有点按极角排序,逆时针偏转

    //第0-2个点，其实不会进入第二重循环的
    //从第3个点开始，就依次检查与凸包中前面点形成的边的偏转方向
    //如果不是逆时针偏转，则弹出该点
    for (int i = 0; i < nN; ++i)
    {
        while (nM >= 2  Cross(ans[nM - 2], ans[nM - 1], pts[i]) <= 0)
        {
            nM--;
        }
        ans[nM++] = pts[i];
    }
}

double GetArea()
{
    double fAns = 0.0;
    Point ori = {0.0, 0.0};
    for (int i = 0; i < nM; ++i)
    {
        fAns += Cross(ori, ans[i], ans[(i + 1) % nM]);
    }
    return fabs(fAns) * 0.5;
}

int main()
{
    while (scanf("%d", &nN) == 1)
    {
        for (int i = 0; i < nN; ++i)
        {
            scanf("%lf%lf", &pts[i].x, &pts[i].y);
            if (pts[i] < pts[0])
            {
                swap(pts[i], pts[0]);//pts[0]是y坐标最小的点
            }
        }

        Scan();//扫描出凸包
        double fArea = GetArea();
        printf("%d\n", (int)(fArea / 50));
    }

    return 0;
}

发表于 分类于 ， 阅读次数： Valine：
本文字数： 4.2k 阅读时长 ≈ 4 分钟

典型的最近点对算法的应用，不过这个题多了个限制条件，就是点分为2类，最短距离必须在不同的类之间。为了满足这个限制，只需要把同类别点直接的距离都当作INF处理即可。
最近点对的算法，算导上面说是nlogn的。但是这个复杂度实现起来略微麻烦点，有一种实现方法是nlognlogn的，其只对x坐标进行了排序。nlogn的算法需要对x和y分量分别进行排序，还需要用到其它的辅助数组。
第一个题我用了nlogn算法实现了，第二个题则用了nlognlogn算法实现了。但是时间上相差不大，因为第一个算法每次进行分治时候消耗的O(n)时间也有几次。第二个算法分治时候，需要再次排序的时间也不一定很多，因为可能数据量不够大。
算法的本质就是二分按照X排序好的点数组，nlognlogn变成n*logn的关键是预先对y也排序好一个点数组，因为按y排序好的点数组，在分治后的合并中要用到。算法更详细的解释请参照算法导论。
poj 3714 代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
#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 代码如下：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
#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;
}

发表于 分类于 ， 阅读次数： Valine：
本文字数： 2.3k 阅读时长 ≈ 2 分钟

题目意思是给出2条直线，然后判断其是否相交，平行，还是重合。刚开始以为是判断2条线段的关系，用了黑书的模板写了，发现连样例都过不了。后面改了很多才过了。先判断2条直线所在的向量是否平行，这个可以判断这2个向量的叉积是否为0，然后再判断线段是否重合，可以选3点判断叉积是否为0。如果向量不平行的话，直接求交点。求交点的公式是用了黑书里面的方法，先求出2个叉积代表2个三角形的有向面积，然后根据定比分点的关系（面积的比例等于交点分其中一条线段的比例）可以推出计算公式。
有叉积和点积这2个工具确实能方便的解决很多问题。

代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
#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;
}

发表于 分类于 ， 阅读次数： Valine：
本文字数： 1.8k 阅读时长 ≈ 2 分钟

这是一个计算几何的题目。题意是，按顺序给一系列的线段，问最终哪些线段处在顶端。只需要穷举判断，当前的线段会与哪些线段有交点即可。也就是暴力求解，但是线段数目N有10的5次方，平方算法是不能过的。这个题能过的原因是题目描述里面说了，top的stick不会超过1000个。那么修改下暴力的方式题目就能过了。
从小到大枚举每个棍子，判断它是否与后面的棍子相交，如果相交直接把当前棍子的top属性置为false，然后break内层循环。这样就不会超时了，暴力也是需要技巧的，这句话说的很对啊。
判断2条线段是否相交的算法直接按照黑书上的模板代码写了，那个模板代码还不错吧。。。

代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
#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;
}

发表于 分类于 ， 阅读次数： Valine：
本文字数： 2.8k 阅读时长 ≈ 3 分钟

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

</div>
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
#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;
}

发表于 分类于 ， 阅读次数： Valine：
本文字数： 1.7k 阅读时长 ≈ 2 分钟

这是一个貌似很麻烦的题，题目要求是将一颗用ascii码绘画出来的树，转换为其一种字符串表示，这种字符串表示好像是叫做什么广义表什么的。
比如，
A

|

B C D

| |

E F G 对应的字符串表示 **(A(B()C(E()F())D(G())))**

</div>
比较纠结的是如何读取数据，如何递归，如果建立树的话，也麻烦，因为还是颗不定叉的树。最主要的是如何方便地递归。最后知道了一个比较巧妙的方法，先一次性把一组数据读入字符串数组里面，再在这个字符串数组上进行递归处理。这样的话，就能很方便的找到树里面节点
的关系了。
而一次读一个字符就想进行递归是没办法确定节点的关系的，不递归估计更很难写，完全没头绪。。。

代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
#include <stdio.h>
#include <stdlib.h>

char szLines[210][210];
int nNumOfLine;

void GetAns(int i, int j)
{
    //printf("i:%d, j:%d, %c\n", i, j, szLines[i][j]);

    if (szLines[i][j] != '\0')
    {
        putchar(szLines[i][j]);
        //printf("%c", szLines[i + 1][j]);
        if (szLines[i + 1][j] == '|')
        {
            int nBeg, nEnd;
            nBeg = nEnd = j;
            while (nBeg >= 0  szLines[i + 2][nBeg] == '-')
            {
                --nBeg;
            }
            while (szLines[i + 2][nEnd] == '-')
            {
                ++nEnd;
            }
            //printf("nBeg:%d, nEnd:%d\n", nBeg, nEnd);
            putchar('(');
            for (int k = nBeg; k             {
                if (szLines[i + 3][k] != ' '  szLines[i + 3][k] != '\0')
                {
                    GetAns(i + 3, k);
                }
            }
            putchar(')');
        }
        else
        {
            printf("()");
        }
    }

}

int main()
{
    int nN;
    char ch;

    scanf("%d", &nN);
    getchar();
    while (nN--)
    {
        nNumOfLine = 0;
        memset(szLines, 0, sizeof(szLines));
        while (gets(szLines[nNumOfLine]), szLines[nNumOfLine][0] != '#')
        {
            //printf("%s\n", szLines[nNumOfLine]);
            nNumOfLine++;
        }
        if (nNumOfLine == 0)
        {
            printf("()\n");
            continue;
        }
        int i, j;
        i = 0;
        for (j = 0; szLines[0][j] == ' '; ++j);
        //printf("i:%d, j:%d\n", i, j);
        putchar('(');
        GetAns(i, j);
        putchar(')');
        putchar('\n');
    }

    return 0;
}

发表于 分类于 ， 阅读次数： Valine：
本文字数： 2.8k 阅读时长 ≈ 3 分钟

这个题目的意思是要计算一些c语言表达式的值。这些表达式有+-还有++，—操作符与a-z这些变量组合而成。a-z的权值是1-26。比如，表达式 c+f—+—a，得出值是9，其它变量的值也需要计算出来。
这个题目感觉比较麻烦，刚开始一点思路也没有，还写了个错误的方法，浪费了时间。后面我的思路是 （+，-） （—，++）（变量）（—，++），这个匹配式子的意思是先处理二元操作符，然后处理前置，再处理变量，再处理后置，如果发现没有后置操作符，则把读取的数据重新写回数据流里面，下次再处理。

代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
#include <stdio.h>
#include <string.h>
#include <sstream>
#include <algorithm>
using namespace std;
struct INFO
{
    char ch;
    int nValue;
    char chAdd;
    bool operator < (const INFO info) const
    {
        return ch < info.ch;
    }
};

INFO infos[200];
char szLine[200];

bool GetNextChar(stringstream ss, char ch)
{
    while (ss >> ch)
    {
        if (ch != ' ');
        {
            return true;
        }
    }
    return false;
}

int main()
{
    while (gets(szLine))
    {
        printf("Expression: %s\n", szLine);
        memset(infos, 0, sizeof(infos));
        stringstream ss(szLine);
        char ch;
        int nNum = 0;
        int nValue = 0;
        char chOper;
        bool bOk = true;
        bool bFirst = true;
        while (1)
        {
            if (bFirst)
            {
                chOper = '+';
                bFirst = false;
            }
            else
            {
                bOk = GetNextChar(ss, ch);
                if (!bOk) break;
                chOper = ch;
            }

            bOk = GetNextChar(ss, ch);
            if (!bOk) break;

            if (ch == '-')//前置--
            {
                bOk = GetNextChar(ss, ch);
                if (!bOk) break;//-
                bOk = GetNextChar(ss, ch);
                if (!bOk) break;//读取字母

                infos[nNum].ch = ch;
                infos[nNum].nValue = ch - 'a';

                if (chOper == '+')
                {
                    nValue += infos[nNum].nValue;
                }
                else
                {
                    nValue -= infos[nNum].nValue;
                }
                ++nNum;
            }
            else if (ch == '+')//前置++
            {
                bOk = GetNextChar(ss, ch);
                if (!bOk) break;//+
                bOk = GetNextChar(ss, ch);
                if (!bOk) break;//读取字母

                infos[nNum].ch = ch;
                infos[nNum].nValue = ch - 'a' + 2;

                if (chOper == '+')
                {
                    nValue += infos[nNum].nValue;
                }
                else
                {
                    nValue -= infos[nNum].nValue;
                }
                ++nNum;
            }
            else
            {
                infos[nNum].ch = ch;
                infos[nNum].nValue = ch - 'a' + 1;

                if (chOper == '+')
                {
                    nValue += infos[nNum].nValue;
                }
                else
                {
                    nValue -= infos[nNum].nValue;
                }
                //读取后置操作符
                char chOne;
                char chTwo;
                bOk = GetNextChar(ss, chOne);
                if (!bOk)
                {
                    ++nNum;
                    break;
                }
                bOk = GetNextChar(ss, chTwo);
                if (!bOk)
                {
                    ++nNum;
                    break;
                }

                if (chOne == chTwo)
                {
                    if (chOne == '+')
                    {
                        infos[nNum].chAdd = '+';
                    }
                    else
                    {
                        infos[nNum].chAdd = '-';
                    }
                }
                else
                {
                    ss.putback(chTwo);
                    ss.putback(chOne);
                }
                ++nNum;
            }
        }

        printf("    value = %d\n", nValue);
        sort(infos, infos + nNum);
        for (int i = 0; i < nNum; ++i)
        {
            if (infos[i].chAdd == '+')
            {
                infos[i].nValue++;
            }
            else if (infos[i].chAdd == '-')
            {
                infos[i].nValue--;
            }
            printf("    %c = %d\n", infos[i].ch, infos[i].nValue);
        }
    }

    return 0;
}

发表于 分类于 ， 阅读次数： Valine：
本文字数： 1.4k 阅读时长 ≈ 1 分钟

题意是用字符串描述的一棵四叉树，读取字符串获得最终叶子节点的颜色。输入是2个字符串，根据这2个字符串建立2个四叉树。然后对于，指定位置的叶子节点，如果2颗树的叶子颜色其中一个为黑色，那么ans++，输出的就是ans。
类似树形结构的东西，直接一个函数递归求解即可。函数参数，一般是字符串地址，当前位置，然后还有其它在递归时候需要用到的东西。

代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
#include <stdio.h>
#define BLACK (1)
#define WHITE (2)
#define MAX (32)
int nStateA[MAX][MAX];
int nStateB[MAX][MAX];

char szOne[10000];
char szTwo[10000];

void GetState(int nState[MAX][MAX], char* pszLine, int nPos,
              int nSize, int nX, int nY)
{
    if (pszLine[nPos] == 'p')
    {
        ++nPos;
        GetState(nState, pszLine, nPos, nSize / 2, nX + nSize / 2, nY);
        GetState(nState, pszLine, nPos, nSize / 2, nX, nY);
        GetState(nState, pszLine, nPos, nSize / 2, nX, nY + nSize / 2);
        GetState(nState, pszLine, nPos, nSize / 2, nX + nSize / 2, nY + nSize / 2);
    }
    else
    {
        for (int i = nX; i < nX + nSize; ++i)
        {
            for (int j = nY; j < nY + nSize; ++j)
            {
                if (pszLine[nPos] == 'e')
                {

                    nState[i][j] = WHITE;
                }
                else
                {
                    nState[i][j] = BLACK;
                }
            }
        }         ++nPos;
    }
}

int main()
{
    int nCases;

    scanf("%d\n", &nCases);
    while (nCases--)
    {
        gets(szOne);
        gets(szTwo);
        int nPos = 0;
        GetState(nStateA, szOne, nPos, MAX, 0, 0);
        nPos = 0;
        GetState(nStateB, szTwo, nPos, MAX, 0, 0);
        int nAns = 0;
        for (int i = 0; i < MAX; ++i)
        {
            for (int j = 0; j < MAX; ++j)
            {
                if (nStateA[i][j] == BLACK || nStateB[i][j] == BLACK)
                {
                    nAns++;
                }
            }
        }
        printf("There are %d black pixels.\n", nAns);
    }

    return 0;
}