上周四做的比赛很纠结，就做出来一道题目。。。。赛后好好总结下，把赛后A的7道题目中自己不太熟悉的算法记录一下。

hdu 3511

D：PrisonBreak

题目不描述：

解题报告：

利用扫描线，把圆形看做类似正方形，判断是否内含。

主要学到了stl的set容器，以前没怎么用过，头一次用，感觉比手写线段树方便不少：

首先定义一个结构体，有自己的排序函数：

struct pint
{
    int y, id;
    pint(int a, int b){y = a, id = b;}
    friend bool operator < (pint a, pint b)
    {
        return a.y < b.y;
    }
};

迭代器：typedef set<pint>::iterator it;

定义：set<pint> jeo;

insert：插入函数。

erase：删除函数。

it a = jeo.insert(...).first;

可以用迭代器接收插入位置，并且位置的左右都是和插入元素“顺序”相邻的。

代码如下：

#include<iostream>
#include<cstdio>
#include<cstring>
#include<set>
#include<algorithm>
#include<cmath>
using namespace std;
struct eve{ int x, id, type;}e[100000];
struct cir{int x, y, r;}x[50000];
bool cmp(eve a, eve b)
{
    if (a.x == b.x) return a.type > b.type;
    return a.x < b.x;
}
struct pint
{
    int y, id;
    pint(int a, int b){y = a, id = b;}
    friend bool operator < (pint a, pint b)
    {
        return a.y < b.y;
    }
};
typedef set<pint>::iterator it;
int n, cnt, ans[50000];
bool inside(int id1, int id2)
{
    long long a = x[id1].r + x[id2].r;
    a *= a;
    long long dis = (long long)(x[id1].x - x[id2].x) * (long long)(x[id1].x - x[id2].x) + (long long)(x[id1].y - x[id2].y) * (long long)(x[id1].y - x[id2].y);
    return dis < a;
}
int main()
{
    while(scanf("%d", &n) != EOF)
    {
        cnt = 0;
        for(int i = 0; i < n; i++)
        {
            scanf("%d%d%d", &x[i].x, &x[i].y, &x[i].r);
            e[cnt].id = i;e[cnt].type = 0;e[cnt++].x = x[i].x - x[i].r;
            e[cnt].id = i;e[cnt].type = 1;e[cnt++].x = x[i].x + x[i].r;
        }
        sort(e, e + cnt, cmp); set<pint> jeo;
        for(int i = 0; i < cnt; i++)
            if (e[i].type == 1)
            {
                jeo.erase(pint(x[e[i].id].y + x[e[i].id].r, e[i].id));
                jeo.erase(pint(x[e[i].id].y - x[e[i].id].r, e[i].id));
            }
            else
            {
                it a = jeo.insert(pint(x[e[i].id].y + x[e[i].id].r, e[i].id)).first;
                it l = a, r = a;
                ans[e[i].id] = 1;
                if (l-- == jeo.begin() || ++r == jeo.end())
                    ans[e[i].id] = 1;
                else
                {
                    if (l->id == r->id && inside(l->id, e[i].id))
                    ans[e[i].id] = ans[l->id] + 1;
                    else
                    {
                        if (inside(l->id, e[i].id) && ans[l->id] + 1 > ans[e[i].id])
                            ans[e[i].id] = ans[l->id] + 1;
                        if (inside(r->id, e[i].id) && ans[r->id] + 1 > ans[e[i].id])
                            ans[e[i].id] = ans[r->id] + 1;
                    }
                    if (l-- != jeo.begin())
                    {
                        if (inside(l->id, e[i].id) && ans[l->id] + 1 > ans[e[i].id])
                            ans[e[i].id] = ans[l->id] + 1;
                        if (l-- != jeo.begin() && inside(l->id, e[i].id) && ans[l->id] + 1 > ans[e[i].id])
                            ans[e[i].id] = ans[l->id] + 1;
                    }
                    if (++r != jeo.end())
                    {
                        if (inside(r->id, e[i].id) && ans[r->id] + 1 > ans[e[i].id])
                            ans[e[i].id] = ans[r->id] + 1;
                        if (++r != jeo.end() && inside(r->id, e[i].id) && ans[r->id] + 1 > ans[e[i].id])
                            ans[e[i].id] = ans[r->id] + 1;
                    }
                }
                jeo.insert(pint(x[e[i].id].y - x[e[i].id].r, e[i].id));
            }
        int re = 1;
        for(int i = 0; i < n; i++) re = max(re, ans[i]);
        printf("%d\n", re);
    }
    return 0;
}