放牧代码和思想
专注自然语言处理、机器学习算法

AOJ 2201 Immortal Jewels 题解 《挑战程序设计竞赛》

目录

AOJ 2201 Immortal Jewels

求婚:有个贵族向一个贫穷的公主求婚,公主提出条件,需要一种“永生宝石”做嫁妆。这种宝石极其稀有,而且极易损毁,所以开采时需要特别小心。如图:

矿工需要使用一种特殊的金属棒开采,宝石呈圆形,矿床是二维平面,每颗宝石坐标为x,y,半径为r,能够吸附在距离m内的金属棒上。一旦金属棒穿过某个宝石,该宝石就被破坏了。

金属棒非常昂贵,只有一根,作为贵族雇佣的程序员,请你帮他算出能开采到的最大宝石数?

数据格式如下:

N

x1 y1 r1 m1

x2 y2 r2 m2

xN yN rN mN

由多个用例组成,输出答案并换行。

3.6与平面和空间打交道的计算几何 

极限情况 

既然金属棒这么稀有,公主为什么不干脆要金属棒算了。

对每个宝石圆,都添加半径扩大m_i的磁力范围圆,将两个圆同时纳入考虑,移动直线的过程中,如果能取到的宝石个数发生变化,那么直线肯定与所有圆中的两个相切,这就是极限情况。所以枚举两个圆的组合确定一条直线,取最大值就行了。

说说很简单,写起来可麻烦了。如果有模板就轻松了,抱着这样的想法我又拿来了osak的模板:

/**
* 对每个宝石圆,都添加半径扩大m_i的磁力范围圆,将两个圆同时纳入考虑
* 移动直线的过程中,如果能取到的宝石个数发生变化,那么直线肯定与所有圆中的两个相切。
* 所以枚举两个圆的组合确定一条直线,取最大值就行了。
*
* 复杂度是O(N^3)。
*/
#include <iostream>
#include <vector>
#include <complex>
#include <cmath>
#include <algorithm>
#include <cassert>

using namespace std;

typedef complex<double> P;
const double PI = acos(-1);
const double EPS = 1e-12;

int cmp(double a, double b)
{
	const double diff = a - b;
	if (fabs(diff) < EPS)
		return 0;
	else if (diff < 0)
		return -1;
	else
		return 1;
}

// 向量点乘
inline double dot(const P &a, const P &b)
{
	return a.real() * b.real() + a.imag() * b.imag();
}

// 向量叉乘
inline double cross(const P &a, const P &b)
{
	return a.real() * b.imag() - b.real() * a.imag();
}

struct line/*{{{*/
{
	P a, b;

	line()
	{}

	line(const P &p, const P &q) : a(p), b(q)
	{}

	// 是否平行
	inline bool parallel(const line &ln) const
	{
		return abs(cross(ln.b - ln.a, b - a)) < EPS;	// 平行叉乘得到向量的模是0,也就是sin(theta)=0 <-> theta=0
	}

	// 是否相交
	inline bool intersects(const line &ln) const
	{
		return !parallel(ln);
	}

	// 求交点
	inline P intersection(const line &ln) const
	{
		const P x = b - a;
		const P y = ln.b - ln.a;
		return a + x * (cross(y, ln.a - a)) / cross(y, x);
	}

	// 点到直线的距离
	inline double distance(const P &p) const
	{
		return abs(cross(p - a, b - a)) / abs(b - a);
	}

	// 求垂足坐标
	inline P perpendicular(const P &p) const
	{
		const double t = dot(p - a, a - b) / dot(b - a, b - a);
		return a + t * (a - b);
	}
};

/*}}}*/

struct circle/*{{{*/
{
	P o;
	double r;

	circle()
	{}

	circle(const P &p, double x) : o(p), r(x)
	{}

	// 通过点 p 的两条切线
	pair<P, P> tangent(const P &p) const
	{
		const double L = abs(o - p);
		const double M = sqrt(L * L - r * r);
		const double theta = asin(r / L);
		const P v = (o - p) / L;
		return make_pair(p + M * (v * polar(1.0, theta)), p + M * (v * polar(1.0, -theta)));
	}

	// 两个半径相等圆的两条平行外切线
	pair<line, line> outer_tangent_parallel(const circle &c) const
	{
		const P d = o - c.o;
		const P v = d * P(0, 1) * r / abs(d);
		return make_pair(line(o + v, c.o + v), line(o - v, c.o - v));
	}

	// 两个圆外切线
	pair<line, line> outer_tangent(const circle &c) const
	{
		if (cmp(r, c.r) == 0)
			return outer_tangent_parallel(c);
		if (r > c.r)
			return c.outer_tangent(*this);
		const P d = o - c.o;
		const double fact = c.r / r - 1;
		const P base = c.o + d + d / fact;
		const pair<P, P> t = tangent(base);
		return make_pair(line(base, t.first), line(base, t.second));
	}

	// 内切线
	pair<line, line> inner_tangent(const circle &c) const
	{
		if (r > c.r)
			return c.inner_tangent(*this);
		const P d = c.o - o;
		const double fact = c.r / r + 1;
		const P base = o + d / fact;
		const pair<P, P> t = tangent(base);
		return make_pair(line(base, t.first), line(base, t.second));
	}

	// 是否相交
	inline bool intersects(const circle &c) const
	{
		return !contains(c) && !c.contains(*this) && cmp(abs(o - c.o), r + c.r) <= 0;
	}

	// 是否相离
	inline bool independent(const circle &c) const
	{
		return cmp(abs(o - c.o), r + c.r) > 0;
	}

	// 两个圆的交点
	pair<P, P> intersection(const circle &c) const
	{
		const double d = abs(o - c.o);
		const double cos_ = (d * d + r * r - c.r * c.r) / (2 * d);
		const double sin_ = sqrt(r * r - cos_ * cos_);
		const P e = (c.o - o) / d;
		return make_pair(o + e * P(cos_, sin_), o + e * P(cos_, -sin_));
	}

	// 是否包含圆c
	inline bool contains(const circle &c) const
	{
		return cmp(abs(o - c.o) + c.r, r) < 0;
	}

	// 是否相交
	inline bool intersects(const line &ln) const
	{
		return cmp(abs(ln.distance(o)), r) <= 0;
	}

	// 圆心到直线的距离
	inline double distance(const line &ln) const
	{
		return abs(ln.distance(o));
	}

	// 圆与直线的交点
	pair<P, P> intersection(const line &ln) const
	{
		const P h = ln.perpendicular(o);
		const double d = abs(h - o);
		P ab = ln.b - ln.a;
		ab /= abs(ab);
		const double l = sqrt(r * r - d * d);
		return make_pair(h + l * ab, h - l * ab);
	}
};

/*}}}*/

void enum_event(const circle &c1, const circle &c2, vector<line> &lines)
{
	if (c1.independent(c2))	// c1 c2相离
	{
		auto outer = c1.outer_tangent(c2);
		lines.push_back(outer.first);
		lines.push_back(outer.second);
		auto inner = c1.inner_tangent(c2);
		lines.push_back(inner.first);
		lines.push_back(inner.second);
	}
	else if (c1.intersects(c2))	// 相交
	{
		auto outer = c1.outer_tangent(c2);
		lines.push_back(outer.first);
		lines.push_back(outer.second);
		auto inter = c1.intersection(c2);
		lines.push_back(line(inter.first, inter.second));	// 此时内切线不存在,使用交点形成的线代替
	}
}

bool solve()
{
	int N;
	cin >> N;
	if (!N)
		return false;

	vector<pair<circle, circle>> jewels;
	vector<line> lines;
	for (int i = 0; i < N; ++i)
	{
		double x, y, r, m;
		cin >> x >> y >> r >> m;
		const P center(x, y);
		pair<circle, circle> jewel = make_pair(circle(center, r), circle(center, r + m));
		for (const auto &other : jewels)
		{
			enum_event(jewel.first, other.first, lines);
			enum_event(jewel.first, other.second, lines);
			enum_event(jewel.second, other.first, lines);
			enum_event(jewel.second, other.second, lines);
		}
		jewels.push_back(jewel);
	}

	int ans = 1;
	for (auto &l : lines)
	{
		int cnt = count_if(jewels.begin(), jewels.end(), [&](const pair<circle, circle> &j) {	// [&] 按引用捕获在lambda表达式所在函数的函数体中提及的全部自动储存持续性变量
			return cmp(j.first.r, j.first.distance(l)) <= 0 && cmp(j.second.r, j.second.distance(l)) >= 0;	// 在磁力圆范围内且不在本体范围内
		});
		ans = max(ans, cnt);
	}
	cout << ans << endl;
	return true;
}

///////////////////////////SubMain//////////////////////////////////
int main(int argc, char *argv[])
{
#ifndef ONLINE_JUDGE
	freopen("in.txt", "r", stdin);
	freopen("out.txt", "w", stdout);
#endif
	cin.tie(0);
	ios::sync_with_stdio(0);

	while (solve());
#ifndef ONLINE_JUDGE
	fclose(stdin);
	fclose(stdout);
	system("out.txt");
#endif
	return 0;
}
///////////////////////////End Sub//////////////////////////////////

上面C++11估计会造成眩晕效果,关于lambda表达式请参考这里

提交结果是:

Judge Not Available的原因据说是后台数据维护。

不过就算AC了公主也不会嫁给你这个穷码农的!

知识共享许可协议 知识共享署名-非商业性使用-相同方式共享码农场 » AOJ 2201 Immortal Jewels 题解 《挑战程序设计竞赛》

分享到:更多 ()

评论 1

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址
  1. #1

    55555555,身为码农,无地自容

    alafeizai2年前 (2015-02-13)回复

我的开源项目

HanLP自然语言处理包基于DoubleArrayTrie的Aho Corasick自动机