HDU 3511 圆扫描线

找最深的圆，输出层数

类似POJ 2932的做法 圆扫描线即可。这里要记录各个圆的层数，所以多加一个维护编号的就行了。

/** @Date    : 2017-10-18 18:16:52

  * @FileName: HDU 3511 圆扫描线.cpp

  * @Platform: Windows

  * @Author  : Lweleth ([email protected])

  * @Link    : https://github.com/

  * @Version : $Id$

  */

#include <bits/stdc++.h>

#define LL long long

#define PII pair<int ,int>

#define MP(x, y) make_pair((x),(y))

#define fi first

#define se second

#define PB(x) push_back((x))

#define MMG(x) memset((x), -1,sizeof(x))

#define MMF(x) memset((x),0,sizeof(x))

#define MMI(x) memset((x), INF, sizeof(x))

using namespace std;

const int INF = 0x3f3f3f3f;

const int N = 1e5+20;

const double eps = 1e-8;

struct yuu

{

	double x, y, r;

	yuu(){}

	yuu(double _x, double _y, double _r):x(_x), y(_y), r(_r){}

};

yuu a[N];

double scanx;

struct cir

{

	int m;

	int flag;

	cir(){}

	cir(int _m, int _f):m(_m), flag(_f){}

	bool operator <(const cir &b) const{

		double dis1 = sqrt(a[m].r * a[m].r - (scanx - a[m].x) * (scanx - a[m].x));

		double dis2 = sqrt(a[b.m].r * a[b.m].r - (scanx - a[b.m].x) * (scanx - a[b.m].x));

		double y1 = a[m].y + dis1 * flag;

		double y2 = a[b.m].y + dis2 * b.flag;

		return y1 < y2|| (fabs(y1 - y2) < eps && flag < b.flag);

	}

};

pair<double ,int> p[N*2];

int ans[N];

int main()

{

	int n;

	while(cin >> n)

	{

		MMF(ans);

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

		{

			double x, y, r;

			scanf("%lf%lf%lf", &x, &y, &r);

			a[i] = yuu(x, y, r);

			p[i*2] = MP(x - r, i);

			p[i*2 + 1] = MP(x + r, i + n);

		}

		sort(p, p + 2 * n);

		set<cir>st;//按交点高度维护圆集合

		int ma = 0;

		for(int i = 0; i < 2 * n; i++)

		{

			scanx = p[i].fi;

			if(p[i].se < n)

			{

				int up = -1, dw = -1;

				st.insert(cir(p[i].se, -1));

				auto pos = st.lower_bound(cir(p[i].se, -1));

				if((++pos) != st.end())

					up = (pos)->m;

				if((--pos) != st.begin())

					dw = (--pos)->m;

				if(up == dw && ~up)

					ans[p[i].se] = ans[up] + 1;

				else if(~up && ~dw)

					ans[p[i].se] = max(ans[up], ans[dw]);

				else ans[p[i].se] = 1;

				//cout << up << dw << endl;

				st.insert(cir(p[i].se, 1));

				ma = max(ma, ans[p[i].se]);

			}

			else

			{

				st.erase(cir(p[i].se%n, 1));

				st.erase(cir(p[i].se%n, -1));

			}

		}

		printf("%d\n", ma);

	}

    return 0;

}