首页 > ACM题库 > HDU-杭电 > HDU 3867-Light and Shadow-计算几何-[解题报告]HOJ
2015
04-13

HDU 3867-Light and Shadow-计算几何-[解题报告]HOJ

Light and Shadow

问题描述 :

Moonfang's Birthday

A nuclear explosion happened and how many sticks on the ground will be illuminated by the radiation? You can assume that the ground is flat, and no radiation can go through the sticks, and any two sticks have no intersections.
To simplify the problem, no two endpoints located on the path of a single radiation.

输入:

For each case, the first line contains the number of sticks n(1~10,000), until the end of file.

The second line includes (sx, sy) to denote the position of explosion center.

Then following n lines are the sticks expressed in (ax, ay) and (bx, by).

输出:

For each case, the first line contains the number of sticks n(1~10,000), until the end of file.

The second line includes (sx, sy) to denote the position of explosion center.

Then following n lines are the sticks expressed in (ax, ay) and (bx, by).

样例输入:

6
0.5 0.5
1.0 -1.0 1.0 1.0
1.5 1.0 1.5 -1.0
2.0 -1.0 2.0 1.0
-1.0 -1.0 -1.0 1.0
-1.5 1.0 -1.5 -1.0
-2.0 -1.0 -2.0 1.0

样例输出:

2

题意:原子弹爆炸,一些互不相交的线段,求能辐射到的线段(可以将原子弹爆炸点视为泛光源)
以辐射源为中心对周围的点按照极坐标角度进行排序,然后在极坐标上使用扫描线方法。
维护一个集合,集合内的元素是与扫描线相交的线段,排序依据是线段与扫描线的交点到辐射源的距离。该集合中的最小元素就是被照射到的线段。

有关容器(set)排序依据的说明:

在扫描线运动前后,如果有两个线段存在于容器中,这两个线段与扫描线的交点到辐射源的距离远近关系不会发生变化。若发生变化,表示扫描线运动范围内两个线段有交点,与题目提供的已知条件不符。

Light and Shadow

PS:此题各种重载 各种stl

#include <cstdio>
#include <cstring>
#include <cmath>
#include <set>
#include <algorithm>
using namespace std;
#define EPS 1e-8
#define LS0(a) (a << 1)
#define LS1(a) ((a << 1) | 1)

const int MAXN = 20010;
struct Point { 
	double x, y;
	Point(double _x = 0.0, double _y = 0.0): x(_x), y(_y) {}
	Point operator + (const Point &b) const {
		return Point(x + b.x, y + b.y);
	}
	Point operator - (const Point &b) const {
		return Point(x - b.x, y - b.y);
	}
	double operator ^ (const Point &b) const {
		return x * b.y - y * b.x;
	}
	bool operator < (const Point &b) const {  //逆时针
		return x * b.y < y * b.x;
	}
	void input() {
		scanf("%lf%lf", &x, &y);
	}
	double diso() {
		return sqrt(x * x + y * y);
	}

}cur,ps[MAXN];

Point lnlncross_pt(Point aa, Point ad, Point ba, Point bd) { // 求直线交点
	ad = ad - aa;
	bd = bd - ba;
	double tmp = bd ^ ad;
	return Point(
		(ad.x * bd.x * (ba.y - aa.y) + aa.x * bd.x * ad.y - ba.x * ad.x * bd.y) / tmp,
		(ad.y * bd.y * (aa.x - ba.x) + ba.y * ad.y * bd.x - aa.y * bd.y * ad.x) / tmp);
}

struct Item { // 扫描线的点类型
	Point *u, *v;
	int type; // 1: 线段起点; 0: 线段终点;
	int sgid; // 线段序号
	Item(Point *_u = NULL, Point *_v = NULL, int _ty = 0, int _id = 0)
		: u(_u), v(_v), type(_ty), sgid(_id) {}
	bool operator < (const Item &b) const {
		if(u == b.u && v == b.v)
			return false;
		Point au = lnlncross_pt(Point(0.0, 0.0), cur, *u, *v);
		Point bu = lnlncross_pt(Point(0.0, 0.0), cur, *b.u, *b.v);
		return au.diso() < bu.diso();
	}

}item[MAXN];

bool flag[MAXN];
set<Item> Scan;

                    
bool cmp(const Item &a, const Item &b) { //极角排序 从-PI到-PI内 
		return atan2(a.u->y, a.u->x) < atan2(b.u->y, b.u->x);

}

void inputps(int n) {
	Point src, a, b;
	src.input();
	for(int i = 0; i < n; ++i) {
		// 读取线段并求得相对于光源的坐标
		a.input(); a = a - src;
		b.input(); b = b - src;
		// 保证线段的极角序
		if(b < a) swap(a, b);
		ps[LS0(i)] = a;
		ps[LS1(i)] = b;
		item[LS0(i)] = Item(&ps[LS0(i)], &ps[LS1(i)], 0, i);
		item[LS1(i)] = Item(&ps[LS1(i)], &ps[LS0(i)], 1, i);
	}
	sort(item, item + 2 * n, cmp);
}



bool sgcross_with_ax(Item &a) {   //与射线相交判断   good 以前不知道的东西
	Point tmp(-1.0, 0.0);
	return (*a.u ^ *a.v) * (*a.u ^ tmp) > 0.0
		&& (*a.u ^ tmp) * (tmp ^ *a.v) > 0.0;
}



int main() {
	int n;
	while(scanf("%d", &n) != EOF) {
		inputps(n);
		memset(flag,0,sizeof(flag));
		// 初始化极角扫描器  初始射线向量为(-1.0,0)
		Scan.clear();
		for(int i = 0; i < 2 * n; ++i) {
		        cur = *item[i].u;
			if(item[i].type == 1 && sgcross_with_ax(item[i]))
				Scan.insert(item[i]);
		}
		// 极角扫描
		for(int i = 0; i < 2 * n; ++i) {
		        cur = *item[i].u;
			if(item[i].type == 1)
				Scan.insert(item[i]);
			else
				Scan.erase(Item(item[i].v, item[i].u, 1, item[i].sgid));
			if(!Scan.empty())
				flag[Scan.begin()->sgid] = true;
		}
		int ans = 0;
		for(int i = 0; i < n; ++i)
			if(flag[i])ans ++;
		printf("%d\n", ans);
	}
	return 0;

}

版权声明:本文为博主原创文章,未经博主允许不得转载。

参考:http://blog.csdn.net/accry/article/details/6676009


  1. 第二个方法挺不错。NewHead代表新的头节点,通过递归找到最后一个节点之后,就把这个节点赋给NewHead,然后一直返回返回,中途这个值是没有变化的,一边返回一边把相应的指针方向颠倒,最后结束时返回新的头节点到主函数。

  2. 有一点问题。。后面动态规划的程序中
    int dp[n+1][W+1];
    会报错 提示表达式必须含有常量值。该怎么修改呢。。