UVa 109 SCUD Busters

解題策略

典型的凸包 (Convex Hull ) 問題。我是採用 Graham's Scan 來解。作法可以參考維基條目 Graham's Scan，我就是照著條目裡的算法原封不動實做的。

本題要找出所有被飛彈摧毀的王國的國土面積總和。過程中一共有兩件事要解決，第一個要知道每個王國的國土面積，第二個要能判斷飛彈落點有沒有打中王國。

求國土面積，要先對王國內的所有的發電廠位置求凸包，然後由凸包去計算多邊形面積 (題目頁有給多邊形面積公式) 。 判斷飛彈落點是否落在國土內，也是以凸包為基礎，沿著凸包的每個邊判斷，如果飛彈落點都在邊的左側，那就表示打中了!

注意

使用Graham's Scan 時要特別注意共線問題，尤其是起始點三點共線，例如 (0,0) (1,1) (2,2) (1,3) ，求出來的凸包應該是 (0,0) (2,2) (1,3)。

閒聊

@2011.10.07
有點囉嗦的題目。2008年底我第一次解這題，因為過程有點曲折，所以花了好幾天才解出來，而且一直搞不定 std::sort( ) 的判斷函數，現在重寫一遍，感覺比較清爽一些了!

	/**
	* UVa 109 SCUD Busters
	* Author: chchwy
	* Last Modified: 2011.10.07
	* Tag: Computational Geometry, Convex Hull
	*/
	#include<cstdio>
	#include<iostream>
	#include<vector>
	#include<algorithm>
	using namespace std;
	struct point
	{
	int x, y;
	};
	// 兩點距離
	int dist (point a, point b)
	{
	return (b.x - a.x) * (b.x - a.x) + (b.y - a.y) * (b.y - a.y);
	}
	// 外積 (p1,p2) (p1,p3)
	int cross (point p1, point p2, point p3)
	{
	return (p2.x - p1.x) * (p3.y - p1.y) - (p2.y - p1.y) * (p3.x - p1.x);
	}
	bool min_y (point a, point b)
	{
	if ( a.y == b.y )
	return (a.x < b.x);
	return (a.y < b.y);
	}
	// Graham's Scan 要將所有的點依照角度排序
	point base;
	bool counter_clockwise(point a, point b)
	{
	int c = cross(base, a, b);
	if ( c == 0 )
	return ( dist(base, a) < dist(base, b));
	return (c > 0);
	}
	class kingdom
	{
	public:
	vector<point> house;
	bool is_destroyed;
	kingdom();
	void convex_hull();
	void destroy(point);
	bool is_inside(point);
	double area();
	};
	kingdom::kingdom()
	{
	is_destroyed = false;
	}
	// 計算凸包: Graham's Scan Algorithm
	void kingdom::convex_hull()
	{
	swap(house[0], *min_element(house.begin(), house.end(), min_y));
	base = house[0];
	sort(house.begin(), house.end(), counter_clockwise);
	house.push_back(house[0]);
	int CH = 1;
	for (int i = 2; i < house.size(); ++i)
	{
	while ( cross(house[CH - 1], house[CH], house[i]) <= 0 )
	{
	if ( CH == 1 )
	{
	house[CH] = house[i];
	i++;
	}
	else
	{
	CH--;
	}
	}
	CH++;
	house[CH] = house[i];
	}
	house.resize(CH + 1);
	}
	void kingdom::destroy (point missile)
	{
	if (is_destroyed)
	return;
	if (is_inside(missile))
	is_destroyed = true;
	}
	// 計算被摧毀的王國面積 (如果沒被摧毀就回傳0)
	double kingdom::area()
	{
	if (!is_destroyed)
	return 0;
	double area = 0;
	for (int i = 1; i < house.size(); ++i)
	area += (house[i - 1].x * house[i].y) - (house[i].x * house[i - 1].y);
	return area / 2;
	}
	// 判斷飛彈落點是否擊中王國
	bool kingdom::is_inside (point missile)
	{
	for (int i = 1; i < house.size(); ++i)
	{
	if ( cross(house[i - 1], house[i], missile) < 0)
	return false;
	}
	return true;
	}
	kingdom build_kindom ( int house_count )
	{
	kingdom k;
	int x, y;
	for (int i = 0; i < house_count; ++i)
	{
	cin >> x >> y;
	k.house.push_back(point{x, y});
	}
	return k;
	}
	int main()
	{
	#ifndef ONLINE_JUDGE
	freopen("109.in", "r", stdin);
	#endif
	// 1. build the world
	vector<kingdom> king;
	int house_count;
	while (cin >> house_count)
	{
	if (house_count == -1)
	break;
	king.push_back(build_kindom( house_count ));
	}
	// 2. do convex hull
	for (int i = 0; i < king.size(); ++i)
	king[i].convex_hull();
	// 3. missiles attack!
	double total_area = 0;
	point missile;
	while ( cin >> missile.x >> missile.y )
	{
	for (int i = 0; i < king.size(); ++i)
	king[i].destroy( missile );
	}
	// 4. calculate the sum of destroyed area
	for (int i = 0; i < king.size(); ++i)
	total_area += king[i].area();
	printf("%.2lf\n", total_area );
	return 0;
	}

view raw 109.cpp hosted with ❤ by GitHub