HDU 4400 Mines（STL）

제목 링크: http://acm.hdu.edu.cn/showproblem.php?pid=4400
제목: 평면 에 n 개의 폭탄 이 있어 서 모든 폭탄 의 중심 과 폭발 범위 d (맨 해 튼 거리, 즉 | x1 - x2 | + | y1 - y2 |) 를 제시 합 니 다.모든 폭탄 에 불 을 붙 일 때 폭발 하 는 폭탄 수 를 출력 하 다.(A 폭탄 의 중심 이 B 폭탄 의 폭발 범위 내 에 있 으 면 B 폭탄 이 폭발 할 때 A 도 폭발한다)
생각:
STL：queue、multiset
함수: unique, lowerbound,upper_bound
우선, x 를 이산 화 하 는 것 은 유 니 크 로 정리 하면 돼, 대단 해...그리고 무 거 운 x 에서 찾 을 때 lowerbound, 2 점 안 써 도 돼, 간단 해...구조 체 y 와 폭탄 의 번 호 를 multiset 에 꽂 으 면 multiset 은 정말 좋 은 물건 이다.연 회 는 불 이 붙 은 모든 폭탄, BFS 에 대해 찾 을 때 x 의 범 위 를 먼저 찾 고 Y 의 범 위 를 찾는다.

#include <iostream>

#include <cstdio>

#include <cstring>

#include <set>

#include <queue>

#include <algorithm>

using namespace std;



struct Node

{

    int y,id;



    Node(){}

    Node(int _y,int _id):y(_y),id(_id){}



    bool operator<(const Node a) const

    {

        return y<a.y;

    }

};



struct Circle

{

    int x,y,d;

};



const int MAX=100005;

multiset<Node> S[MAX];

multiset<Node>::iterator L,R,it;

int hash[MAX],n,m,num=0,visit[MAX],X;

Circle a[MAX];





int ABS(int x)

{

    if(x<0) return -x;

    return x;

}



void deal()

{

    printf("Case #%d:
",++num);

    memset(visit,0,sizeof(visit));

    int A,B,i,t,ans,y;

    queue<int> Q;

    for(scanf("%d",&m);m--;)

    {

        scanf("%d",&t);

        t--;

        if(visit[t])

        {

            puts("0");

            continue;

        }

        while(!Q.empty()) Q.pop();

        Q.push(t);

        visit[t]=1;

        ans=0;

        while(!Q.empty())

        {

            ans++;

            t=Q.front();

            Q.pop();

            A=lower_bound(hash,hash+X,a[t].x-a[t].d)-hash;

            B=upper_bound(hash,hash+X,a[t].x+a[t].d)-hash;

            for(i=A;i<B;i++)

            {

                y=a[t].d-ABS(a[t].x-hash[i]);

                L=S[i].lower_bound(Node(a[t].y-y,0));

                R=S[i].upper_bound(Node(a[t].y+y,0));

                for(it=L;it!=R;it++)

                {

                    if(!visit[it->id])

                    {

                        visit[it->id]=1;

                        Q.push(it->id);

                    }

                }

                S[i].erase(L,R);

            }

        }

        printf("%d
",ans);

    }

}



int main()

{

    while(scanf("%d",&n),n)

    {

        int i,k;

        for(i=0;i<n;i++)

        {

            scanf("%d%d%d",&a[i].x,&a[i].y,&a[i].d);

            hash[i]=a[i].x;

        }

        sort(hash,hash+n);

        X=unique(hash,hash+n)-hash;

        for(i=0;i<n;i++) S[i].clear();

        for(i=0;i<n;i++)

        {

            k=lower_bound(hash,hash+X,a[i].x)-hash;

            S[k].insert(Node(a[i].y,i));

        }

        deal();

    }

    return 0;

}