自动搬运

查看原文

来自洛谷，原作者为

	feicheng State of Emergency

搬运于2025-08-24 22:27:04，当前版本为作者最后更新于2020-12-23 21:22:09，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

P7150 题解

思路

经过一段时间，每头奶牛的身后会留下一条被啃秃了的轨迹。

这一句给了我们很关键的提示：奶牛的轨迹是一条线

所以可以将奶牛根据行进方向的不同分成两类

因为所有的奶牛的x，y坐标都不相同。

意味着向北走的奶牛只会被向东走的奶牛阻挡，向东走的奶牛只会被向北走的奶牛阻挡。

那么如何判断每头奶牛阻挡的个数呢？

观察数据范围发现：只可能从奶牛的行进方向入手（因为x,y的取值过大）。 所以我们可以将每一头奶牛的路径“画出来”。但是这样还是不能避免涉及过多坐标的问题。所以还需要精简。

考虑奶牛什么时候会停下：当且仅当方向不同且已行进路程的两头奶牛相遇时，才会有一头奶牛停下。所以我们可以

维护交点

是的，只需要维护每头牛走过的线的交点即可。所以现在重点就是如何记录交点以及交点需要存储哪些信息。

首先我们要考虑哪些奶牛可以产生交点。

产生交点的条件：

1. 两头奶牛的方向不同
2. 假设向东走的奶牛为$c_e$,向北走的奶牛为$c_n$，则奶牛要相遇的条件为

$c_e.x < c_n.x$ 且 $c_e.y > c_n.y$

这个结论很好推，因为对于$c_n$，它的$x$坐标是不变的，所以如果一开始$c_e$的$x$坐标就比$c_n$大，那么很显然不能交上，$y$坐标同理

现在我们已经有了一张偌大的图，图上有若干个交点，那么我们应该维护哪些信息呢？

假设现在有一个交点$P$,由两头牛$N,E$相交得到，那么我们现在要判断哪一头牛会被挡住，只需判断两头牛起始点距交点的距离即可（很显然距离大的会被挡住）。

所以交点维护的信息已经一目了然：

交点坐标，由哪两条线相交而来（存储线的编号）。

但现在又有一个问题了：有的牛会被挡住，它实际上只走了一个线段，但是我们存储的仍然是一条射线。

这个问题其实很好解决，我们可以设置一个删除数组，维护每一头牛有没有被挡住，那么在交点判断时，如果有牛被挡住了，很显然这个交点是不存在的。 那么对于没有被挡住的牛，他挡住的牛的个数应该是

他本身挡住的牛的个数 + 他挡住的另一头牛挡住的牛的个数 + 1（另一头牛本身）

最后一个问题：判断交点顺序

相交距离越小的点越先被判断。那么哪些点的距离比较小呢？

很显然是左下角的点（因为牛是往右或者上走的）。

所以我们要对交点进行排序，以$x$坐标和$y$坐标的任意一个作为第一关键字排序,另一个作为第二关键字排序（从小到大），然后判断交点即可。

接下来上代码：

#include <bits/stdc++.h>
#define ll long long
#define ri register int
using namespace std;
struct cows{
	int x,y,num;
}c[1100],nth[1100],est[1100];//结构体维护奶牛的信息
//x，y为坐标，num为输入的编号（因为之后要把奶牛存到两个数组里去）
//nth数组是向北走的奶牛的集合，est是向东的 
struct point{
	int x,y;
	int numx,numy;
	bool operator < (const point others) const
	{
		if(this->x  == others.x){
			return this->y < others.y;
		}
		return this->x < others.x;
	}//重载运算符，当然写比较函数也可 
}p[1100 * 1100 /4];//交点维护坐标和相交奶牛的编号 
int n,cntn,cnte,cntp,ans[1100];
bool del[1100];//删除数组 
int main(void)
{
	ios::sync_with_stdio(false);
	cin>>n;
	for(int i = 1;i <= n;i++){
		char x;
		cows tmp;
		cin>>x>>tmp.x>>tmp.y;
		tmp.num = i;
		if(x == 'N'){
			c[i] = tmp;
			nth[++cntn] = tmp;
		}
		else{
			c[i] = tmp;
			est[++cnte] = tmp;
		}
	}//输入不解释 
	for(int i = 1;i <= cntn;i++){
		for(int j = 1;j <= cnte;j++){
			if(nth[i].x > est[j].x && nth[i].y < est[j].y){
				p[++cntp].x = nth[i].x;
				p[cntp].y = est[j].y;
				p[cntp].numx = est[j].num;
				p[cntp].numy = nth[i].num;
			}//建立交点 
		}
	}
	sort(p + 1,p + 1 + cntp);
	for(int i = 1;i <= cntp;i++){
		if(del[p[i].numx] || del[p[i].numy]){
			continue;//如果有一头牛被挡住，说明交点不存在了 
		}
		int dx = p[i].x - c[p[i].numx].x;
		int dy = p[i].y - c[p[i].numy].y;//计算距离 
		if(dx < dy){
			del[p[i].numy] = 1;
			ans[p[i].numx] = ans[p[i].numx] + ans[p[i].numy] + 1;
		}
		if(dx > dy){
			del[p[i].numx] = 1;
			ans[p[i].numy] = ans[p[i].numy] + ans[p[i].numx] + 1;
		}
	}
	for(int i = 1;i <= n;i++){
		cout<<ans[i]<<endl;
	}
	return 0;
}

蒟蒻第一次写题解，希望能过