CDOJ 26 遮挡判断(shadow) 解题报告

题目链接http://acm.uestc.edu.cn/#/problem/show/26

出题目的给我说清东边是哪一边啊魂淡！

分析样例可得，东边是先读入数据的那一边。

这题主要考察排序，然而感谢上苍我有<algorithm>

另外，CDOJ是可以用C++11标准的匿名函数的，所以sort的比较函数我就打了匿名的

这题只要记录一下扫到的柱子中投影最西边最靠西的那根，不妨设为柱子h

如果这根柱子h能完全遮住当前扫到的柱子i，那么柱子h仍然是影子最靠西的柱子

如果这根柱子h不能完全遮住当前扫到的柱子i，那么柱子i的投影末端就是最靠西的，更新一下就可以了

判断是不是完全遮住简单的，看如果柱子顶端间的正切值比给出的大，那么就可以遮住了啦

为了不使用到坑爹的浮点数，可以，乘过去，就像：[frac{H_h-H_i}{X_i-X_h} geq frac{T}{A}]

[A(H_h-H_i)geq T(X_i-X_h)]

#include <algorithm>
#include <cstdio>
using namespace std;

int N;
struct Pillar {
	int X, H;
} p[100005];
int T, A;
int shade;

int main() {
	while (~scanf("%d", &N) && N) {
		shade = 0;
		for (int i = 0; i < N; ++i)
			scanf("%d%d", &p[i].X, &p[i].H);
		scanf("%d/%d", &T, &A);
		sort(p, p + N, [](Pillar x, Pillar y){ return x.X < y.X; });
		int h = 0;
		for (int i = 1; i < N; ++i) {
			if (A * (p[h].H - p[i].H) >= T * (p[i].X - p[h].X))
				++shade;
			else h = i;
		}
		printf("%d
", N - shade);
	}
	return 0;
}